Positive integer \textbf{A} is a divisor of an integer \textbf{B} if \textbf{B} can be divided by \textbf{A} without remainder. For exemple, \textbf{15} has \textbf{4} divisirs: \textbf{1}, \textbf{3}, \textbf{5}, \textbf{15}. Your task is to determinate whether the number of divisors of a given integer is even or odd. \textbf{Input} The first line of the input file contains one integer number \textbf{N} (\textbf{1} <= \textbf{N} <= \textbf{100}). The second line contains \textbf{N} integers \textbf{X_i} (\textbf{1} <= \textbf{X_i}10^18). Numbers in the line are space-separated. \textbf{Output Tje only line of the output file must contain N numbers separated by spaces. The i-th number should be 0, if the number of divisiors of X_i is even, and 1 otherwise.}