divisors

For a given positive integer determine if its even or odd divisors or or neither of them are in majority.

Example

    The positive divisors of 7: 1 and 7 - the majority are odd.
    For 8: 1,2,4 and 8 - the majority are even.
    10: 1,2,5 and 10 - no majority, it has equal number of odd and even divisors.

Input Specification

N
a1
...
aN

The number 1 ≤ N ≤ 103 in the first line is the amount of integers to be processed. Each of the subsequent N lines consists a single integer 1 ≤ ak ≤ 1012.

Output Specification

For each integer ak in the input, write a line with a single number 1,2 or 0 if ak's odd divisors, even divisors or neither of them are in majority, respectively.

Sample Input 1

1. 3
2. 7
3. 8
4. 10

download as text file

Sample Output 1

1. 1
2. 2
3. 0

download as text file

Sample Input 2

1. 5
2. 2
3. 4
4. 6
5. 8
6. 10

download as text file

Sample Output 2

1. 0
2. 2
3. 0
4. 2
5. 0

download as text file