Дуже складна...

Додатнє число A називається дільником числа B, якщо число B ділиться на A без остачі. Наприклад, у числа 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 непарна.

Приклади