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.
Sample Input
2
2
3
Sample Output
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.
