CF1338C Perfect Triples

考虑一个由正整数构成的无限序列 $s$，其生成方式如下： 1. 找到字典序最小的正整数三元组 $(a, b, c)$，满足： - $a \oplus b \oplus c = 0$，其中 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 - $a$、$b$、$c$ 均不在序列 $s$ 中。 这里，若三元组 $(a_1, b_1, c_1)$ 的序列 $[a_1, b_1, c_1]$ 在字典序上小于三元组 $(a_2, b_2, c_2)$ 的序列 $[a_2, b_2, c_2]$，则称前者字典序更小。 2. 按顺序将 $a$、$b$、$c$ 添加到 $s$ 的末尾。 3. 回到第一步，继续上述过程。 现在给定一个整数 $n$，请你求出序列 $s$ 的第 $n$ 个元素。 你需要回答 $t$ 组独立的测试用例。 一个序列 $a$ 在字典序上小于序列 $b$，当且仅当在第一个不同的位置，$a$ 的元素小于 $b$ 的对应元素。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 接下来的 $t$ 行，每行包含一个整数 $n$（$1 \le n \le 10^{16}$），表示你需要查询的元素在序列 $s$ 中的位置。

对于每个测试用例，输出一行答案，表示序列 $s$ 的第 $n$ 个元素。

序列 $s$ 的前若干项为 $1, 2, 3, 4, 8, 12, 5, 10, 15, \dots$。 由 ChatGPT 4.1 翻译