Очень сложная задача

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

Напишите программу, которая определяет, имеет ли заданное число четное или нечетное количество делителей.

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

Первая строка ввода содержит целое число N (1 ≤ N ≤ 100), вторая строка содержит N целых чисел X_i (1 ≤ X_i ≤ 10^18). Числа разделены пробелами.

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

Выведите N целых чисел. i-е число должно быть 0, если количество делителей X_i четное, и 1, если количество делителей X_i нечетное.

Примеры