Programming contests

DEIK Regionális Programozó Csapatverseny, középiskolai kategória, 2022. december 4.

December 4, 2022 10:00 AM – December 4, 2022 3:15 PM

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`

1. `1`
2. `2`
3. `0`

Sample Input 2

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