C. Perfect Triplestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputConsider the infinite sequence s of positive integers, created by repeating the following steps:  Find the lexicographically smallest triple of positive integers (a, b, c) such that   a \oplus b \oplus c = 0, where \oplus denotes the bitwise XOR operation.  a, b, c are not in s.  Here triple of integers (a_1, b_1, c_1) is considered to be lexicographically smaller than triple (a_2, b_2, c_2) if sequence [a_1, b_1, c_1] is lexicographically smaller than sequence [a_2, b_2, c_2].  Append a, b, c to s in this order.  Go back to the first step. You have integer n. Find the n-th element of s.You have to answer t independent test cases.A sequence a is lexicographically smaller than a sequence b if in the first position where a and b differ, the sequence a has a smaller element than the corresponding element in b.InputThe first line contains a single integer t (1 \le t \le 10^5) — the number of test cases.Each of the next t lines contains a single integer n (1\le n \le 10^{16}) — the position of the element you want to know.OutputIn each of the t lines, output the answer to the corresponding test case.ExampleInput
9
1
2
3
4
5
6
7
8
9
Output
1
2
3
4
8
12
5
10
15
NoteThe first elements of s are 1, 2, 3, 4, 8, 12, 5, 10, 15, \dots 
9
1
2
3
4
5
6
7
8
9

1 2 3 4 8 12 5 10 15 
['bitmasks', 'brute force', 'constructive algorithms', 'divide and conquer', 'math', '*2200']