Even? Odd?

Interview

Time limit2sMemory limit256 MB

Summary

Decide for each of up to 100 numbers up to 1e18 whether its divisor count is odd or even.

Level: Easy3 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

If the remainder of $B$ divided by $A$ is $0$ , then $A$ is a divisor of $B$ . ( $A > 0$ , $B > 0$ ) For example, the divisors of $15$ are $1$ , $3$ , $5$ , $15$ .

Decide whether a given number has an odd or an even number of divisors.

Input

The first line contains the number of tests $N$ . ( $1 \le N \le 100$ )

The second line contains $N$ numbers $X$ , separated by spaces, whose divisor counts you must classify. ( $1 \le X \le 10^{18}$ )

Output

For each number print $1$ if its divisor count is odd and $0$ if it is even. Print the $N$ answers on one line in the input order, separated by single spaces.

Examples2

Example 1
Input
```
2
4 5
```
Expected output
```
1 0
```
Example 2
Input
```
1
1
```
Expected output
```
1
```