Ali baba did a trick on the forty thieves and was able to trap them inside a big cave which was the home of wild wolves. The thieves are without any weapons, only the chief of the thieves has knife. With no weapons they will not be able to fight with the wolves, so they decide to kill themselves rather than being eaten alive.

They all decide that they will stand in a circle and they every third person will kill himself but the chief of the thieves does not like this idea and has no intention of killing himself. He calculates where should he stand so that he is the last one left.

HackerMan wants to build a game based on this story, but instead of killing he decides that the participant will leave the game, and instead of every 3rd position it will be every 2nd position. Of course the number of participants will be much more than 40 in this game.

Input

The first line of input is an integer N (1 <= N <= 1000) that specifies the number of test cases. After that every line contains an integer X (5 <= X <= 100000000) which is the number of participants in the game.

Output

For each test case generate a line containing the position of the participant who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2.