Interesting sequence

The sequence 011212201220200112... is built next way: first goes 0, then the next action is repeated: append the already existing sequence to the right, replacing 0 with 1, 1 with 2 and 2 with 0, i.e.

0 → 01 → 0112 → 01121220 → ...

Find the m-th digit of the sequence.

Input

First line contains the number of tests n (1 ≤ n ≤ 1000). Each of the next n lines contains m (1 ≤ m ≤ 2^63 - 1) - the number of required digit in the sequence.

Output

For each test case print in a separate line the digit at the m-th place in the given sequence.

Examples