Problems
Interesting sequence
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 ≤ 263
- 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.
Input example #1
3 17 239 385
Output example #1
1 0 2