raju-and-manu

Raju and Manu are best friends. Manu loves mathematics. Raju keeps on querying Manu and Manu always solves his problem. One day Raju tries to trick Manu. He knows that his friend has a weak hand in base conversion. So he gives Manu an integer N and asks him to find the largest number from 0 to N (both inclusive) whose binary has maximum arithmetic sum of digits. 
It seems our Manu got stuck and he has asked for your help. Help him help him to figure out that number.

INPUT

The first line of input contains an integer T denoting the number of test cases.
Each test case consist a single line containing an integer N.

OUTPUT

Output contains T lines, each line containing the solution to the respective test cases.

CONSTRAINTS
1 ≤ T ≤ 1000
1 ≤ N ≤ 100000

SAMPLE INPUT
1
4

SAMPLE OUTPUT
3

Explanation

Decimals from 0 to 4 can be represented in binary as {000, 001, 010, 011, 100}.Out of these ‘3’ has largest digit sum i.e. 0+1+1=2.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: