Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

Stockholm Numbers are positive integers which when we write it in binary it has even digits 1. Can you tell me the K-th Stockholm Number?

Input

The first line of input is the number of test case. For each test case, There is only one line contains only one integer K. There is a blank line before each test case. 1 <= K <= 10^9

Output

For each test case output the answer on a single line.

Sample Input

3 1 2 3

Sample Output

3 5 6

Source

8th SCUPC

Author

windy7926778