Positive integer \textbf{А} is called a divisor of \textbf{В} if \textbf{A} divides \textbf{B} without remainder. For example, integer \textbf{15} has \textbf{4} divisors: \textbf{1},\textbf{3}, \textbf{5}, \textbf{15}. Write a program that will find whether particular number has even or odd number of divisors. \InputFile The first line of input contains integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{100}), the second line contains \textbf{N} integers \textbf{X_i} (\textbf{1} ≤ \textbf{X_i} ≤ \textbf{10^18}). Integers are split by spaces. \OutputFile Output should contain \textbf{N} integers. \textbf{і}--th number should be \textbf{0} if number of divisors of \textbf{X_i} is even, and \textbf{1}, if number of divisors of \textbf{X_i} is odd.