It is good to hav an auspicious start to any event.The kruzade OPC team felt that online coding event should
also have an auspicious start.As a mark of auspiciousness, we define good sequence as follows:
A good number is defined as a non-negative number that has an odd number of 1s in its binary
expansion(that is when the decimal number is converted to base 2).
for eg.
1=1  num of 1s in binary equiv=1(odd) so,1 is a good number
2=10 num of 1s in binary equiv=1(odd) so,2 is a good number
3=11 num of 1s in binary equiv=2(even) so,3 is not a good number

The good sequence is the collection of good numbers.
The good sequence goes like this:
1,2,4,7,8,11,13,14,16,19...

You have been hired to find out the nth good number in the sequence.

Input

First line contains an integer T, representing the number of test-cases. Then T lines
follow each containing one integer n, 1 <= n <= 500.

Output

For each test case output on a line the nth good number in the sequence.

Example

Input:
3
10
5
20

Output:
19
8
38