Problem Description

In order to remember history, King plans to play losephus problem in the parade gap.He calls $n (1\le n\le 5000)$ soldiers, counterclockwise in a circle, in label $1, 2, 3... n$.

The first round, the first person with label $1$ counts off, and the man who report number $1$ is out.

The second round, the next person of the person who is out in the last round counts off, and the man who report number $2$ is out.

The third round, the next person of the person who is out in the last round counts off, and the person who report number $3$ is out.



The N - 1 round, the next person of the person who is out in the last round counts off, and the person who report number $n-1$ is out.

And the last man is survivor. Do you know the label of the survivor?

Input

The first line contains a number $T(0 < T \le 5000)$, the number of the testcases.

For each test case, there are only one line, containing one integer $n$, representing the number of players.

Output

Output exactly $T$ lines. For each test case, print the label of the survivor.

2
2
3

2
2

Hint:
For test case #1：the man who report number $1$ is the man with label $1$, so the man with label $2$ is survivor.

For test case #1：the man who report number $1$ is the man with label $1$, so the man with label 1 is out. Again the the man with label 2 counts $1$,  the man with label $3$ counts $2$, so the man who report number $2$ is the man with label $3$. At last the man with label $2$ is survivor.