Description
In order to remember history, King plans to play losephus problem in the parade gap.He calls n(1≤n≤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≤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
