Reflect

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

We send a light from one point on a mirror material circle,it reflects $N$ times and return the original point firstly.Your task is calcuate the number of schemes.


Input

First line contains a single integer $T (T \leq 10)$ which denotes the number of test cases.

For each test case, there is an positive integer $N (N \leq 10^{6})$.

Output

For each case, output the answer.

Sample Input

1 4

Sample Output

4

Hint

hujie

Source

BestCoder Round #54 (div.2)

提交代码