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

Входные данные

Первая строка входного файла содержит целое число N (1 <= N <= 100). Следующая строка содержит N чисел Xi (1 <= Xi <= 1018). Числа в строке разделены пробелами.

Выходные данные

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