Princu, yes the one and only Prince on top of gnidoc spectrum of Ruprimah. The sweetest, most gentle and the best person in Ruprimah was on a walk when he found Suyash and Bimal playing with a set of natural numbers. Imagine the game as a game of badminton between Suyash and Bimal where the set represents the shuttle. Suyash is standing on the left and Bimal on right. With every knock on the set all the alternate characters from the side of knock would fall. In every game Suyash will serve first and they will just bounce the set back and forth. The game will end when there is only one number left. They both decided to give that number to Princu as a token of respect. Find what gift will Princu get.

Example For N = 8, the states of the set are

(1,2,3,4,5,6,7,8) -> (2,4,6,8) -> (2,6) -> (6)

Princu is gifted the number 6.

INPUT

First line contains an integer T denoting the number of test cases.

Next T lines contain an integer N denoting the first N Natural numbers in the set.

OUTPUT

For each N print the gift Princu will get for that game in a newline.

CONSTRAINTS

1 <= T <= 10^6

1 <= N <= 10^19