# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* raysh07

*sushil2006*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

Cakewalk

# PREREQUISITES:

None

# PROBLEM:

Given an integer N, decide whether N has more even divisors then odd divisors or vice versa.

# EXPLANATION:

Since the constraints are quite small — N is \leq 100 — it suffices to simply bruteforce over the all the divisors of N to count which of them are even and which are odd.

This is enough get AC - however, there also exists a much faster solution, which requires a bit of casework.

Observe that:

- If N is odd, every divisor of N is also odd; so surely it has more odd divisors than even divisors.
- If N is a multiple of 4, it will always have more even divisors than odd divisors.
- To see why, consider some odd divisor d of N. Since N is a multiple of 4, both 2d and 4d must also divide N.
- So, for each odd divisor of N, we obtain (at least) two even divisors - meaning N has more even than odd divisors.

- If N is even but not a multiple of 4, the number of even and odd divisors will be equal.

This follows from similar logic to the previous case:- For each odd divisor d, 2d will also be a divisor of N which is even.
- For each even divisor d of N, \frac{d}{2} will be an odd divisor of N since N isn’t divisible by 4.
- So, all the divisors of N break up into (even, odd) pairs this way, meaning there’s an equal number of even and odd divisors.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# CODE:

## Editorialist's code (PyPy3)

```
for _ in range(int(input())):
n = int(input())
if n%4 == 0: print(1)
elif n%4 == 2: print(0)
else: print(-1)
```