Interesting sequence#4894
The sequence 011212201220200112... is built next way: first goes , then the next action is repeated: append the already existing sequence to the right, replacing with , with and with , i.e.
0 → 01 → 0112 → 01121220 → ...
Find the -th digit of the sequence.
First line contains the number of tests (1 \leq n \leq 1000). Each of the next lines contains (1 \leq m \leq 2^{63} - 1) - the number of required digit in the sequence.
For each test case print in a separate line the digit at the -th place in the given sequence.
Example 1