Binary vs. Negative Binary#2693
The negative binary system is a positional numeral system with base . As in the binary system, any non-negative integer can be represented in this system. For example, 3_{10} = 111_{-2}. The negative binary system can also represent negative numbers as easily as positive ones: -3_{10} = 1101_{-2}. Some numbers have identical representations in both the binary and negative binary systems. In this problem, you are to find the -th integer whose representation is the same in both systems.
The first line contains the number of test cases. Each of the next lines contains an integer (1 < N \leq 10^9).
For each test case, output the -th integer whose representation is the same in both the binary and negative binary systems, each on a separate line.
Example 1