Even? Odd?

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

Easy3Number theoryMathInterviewNo attempts yetTime limit2sMemory limit256 MB

Description

Examples2

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.