5643：King's Game

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?

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 exactly $T$ lines. For each test case, print the label of the survivor.