Bounce Bounce Bounce

Time limit3sMemory limit512 MB

Summary

Count laser directions that bounce off a circular mirror exactly N times and return to the start for the first time.

Level: Medium7 of 10
Topics: Math, Number theory, Geometry, Combinatorics
Solved: No attempts yet

Problem

Fidel built a circular ring. Its inner boundary is made of reflective material, and a laser sits at one point of the boundary. Fidel wants to aim the laser so that the beam bounces off the boundary exactly $N$ times and then returns to its starting point for the first time. How many initial directions can he choose?

The angle of incidence equals the angle of reflection. See the image below. The position of the laser in the image is only for demonstration.

Input

The first line contains $T$ , the number of test cases.

Each test case is a single line holding one integer $N$ .

Constraints

$1 \le T \le 3000$
$1 \le N \le 10^9$

Output

For each test case, print on its own line the number of initial directions that make the beam bounce exactly $N$ times and then return to the starting point for the first time.

Hint

For $N = 4$ there are exactly four ways to bounce four times and come back to the starting point. The figure below shows all of them.

For $N = 3$ there are exactly two ways to bounce three times and come back to the starting point.

Examples2

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