Районная олимпиада по информатике 2009 года за 9 класс | Казахстанские олимпиады

Задача B. Делители

Положительное число $A$ называется делителем числа $B$, если число $B$ делится на $A$ без остатка. Например, у числа 15 есть 4 делителя: 1, 3, 5, 15. Для каждого из заданных чисел вам необходимо определить, четно или нечетно количество его делителей.

Формат входного файла

Первая строка входного файла содержит целое число $N$ ( $1 <= N <= 10$ ). Следующая строка содержит $N$ чисел $X_i$ ( $1 <= X_i <= 10^{18}$ ). Числа в строке разделены пробелами

Формат выходного файла

Единственная строка выходного файла должна содержать $N$ чисел разделенных пробелом. i-е число должно быть $0$, если количество делителей $X_i$ четно, и $1$, если количество делителей $X_i$ нечетно.

Примеры

Вход

2
4 5

Выход

1 0