The Very Hard One

Positive integer A is a divisor of an integer B if B can be divided by A without remainder. For exemple, 15 has 4 divisirs: 1, 3, 5, 15. Your task is to determinate whether the number of divisors of a given integer is even or odd.

Input The first line of the input file contains one integer number N (1 <= N <= 100). The second line contains N integers X_i (1 <= X_i10^18). Numbers in the line are space-separated. 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.

Examples