The Very Hard One#249
Positive integer A is a divisor of integer B if can be divided by without a remainder. For example, has divisors: , , , . You are required to determine whether the number of divisors of each given integer is even or odd.
The first line contains the integer (1 \le N \le 100). The second line contains integers X_i (1 \le X_i \le 10^{18}), separated by spaces.
Output a single line with numbers separated by spaces. The -th number should be if the number of divisors of X_i is even, or if it is odd.
Example 1