Batman is trying to penetrate the ranks of the League of Assasins but the league is ever scrutinizing now. They have built a death game that chooses the worthy for the senior ranks. Batman must survive at the end of the game to be successful in his mission. He needs your help. There are N of participants standing in a circle, 1 to N. Game starts with the participant 1 killing the next participant, at position 2. The next alive participant, 3, kills the adjacent alive participant, 4. The game goes on as: 1 kills 2, 3 kills 4, 5 kills 6......... until there is only one survivor. Help Batman choose the position to be that survivor.

Constraints
1<=T<=10^6
1<=N<=10^9

Input: The first line takes an input T, denoting the number test cases. Next T lines follow. Each of the T lines contains a single integer N that denotes the number of participants in the death game.

Output: For each of the test case, output a single integer in a new line denoting the final surviving position.

**Contributed** by **maytan.thegeek@gmail.com (Tanmay)**