Додатнє число \textbf{A} називається дільником числа \textbf{B}, якщо число \textbf{B} ділиться на \textbf{A} без остачі. Наприклад, у числа \textbf{15} є \textbf{4} дільника: \textbf{1}, \textbf{3}, \textbf{5}, \textbf{15}. Вам потрібно визначити, парна чи непарна кількість дільників кожного з заданих чисел. \textbf{Вхідні дані} Перший рядок вхідного файлу містить ціле число \textbf{N} (\textbf{1} <= \textbf{N} <= \textbf{100}). Наступний рядок містить \textbf{N} чисел \textbf{X_i} (\textbf{1} <= \textbf{X_i} <= \textbf{10^18}). Числа у рядку відокремлені пропусками. \textbf{Вихідні дані} Єдиний рядок вихідного файлу повинен містити \textbf{N} чисел, відокремлених пропусками. \textbf{i}-е число повинно бути \textbf{0}, якщо кількість дільників \textbf{X_i} парна, або \textbf{1}, якщо кількість дільників \textbf{X_i} непарна.