C. Perfect Triples
bitmasks; brute force; constructive algorithms; divide and conquer; math
Consider 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\).
The 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.
In each of the \(t\) lines, output the answer to the corresponding test case.
The first elements of \(s\) are \(1, 2, 3, 4, 8, 12, 5, 10, 15, \dots \)