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.
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.
For each test case print in a separate line the digit at the m-th place in the given sequence.