Binary vs. Negative Binary

The negative binary system is a positional numeral system with a base of (-2). Similar to the standard binary system, it can represent any non-negative integer. For instance, (3_10) is represented as (111_-2). Interestingly, the negative binary system can also represent negative numbers as easily as positive ones: (-3_10) is expressed as (1101_-2). Some numbers have identical representations in both the binary and negative binary systems. In this task, your goal is to determine the (n)-th integer that shares the same representation in both systems.

Input

The first line of the input file specifies the number of test cases. Each subsequent line contains a single integer (N) ((1 < N $\le$ 10^9)).

Output

For each test case, output the (n)-th integer that has the same representation in both the binary and negative binary systems, each on a separate line.

Examples