Дуже складне завдання

Ціле додатне число 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 непарна.

Приклади