CF1338C.Perfect Triples

Consider the infinite sequence $s$ of positive integers, created by repeating the following steps:

1. 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]$.
2. Append $a$, $b$, $c$ to $s$ in this order.
3. 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$.

考虑由以下步骤重复生成的正整数无限序列 $s$：

1. 找到字典序最小的正整数三元组 $(a, b, c)$，满足：
   • $a \oplus b \oplus c = 0$，其中 $\oplus$ 表示按位异或运算；
   • $a$、$b$、$c$ 均尚未出现在序列 $s$ 中。
     这里，三元组 $(a_1, b_1, c_1)$ 被认为字典序小于三元组 $(a_2, b_2, c_2)$，当且仅当序列 $[a_1, b_1, c_1]$ 字典序小于序列 $[a_2, b_2, c_2]$。
2. 将 $a$、$b$、$c$ 按此顺序追加到 $s$ 的末尾。
3. 返回第 1 步继续执行。

给定整数 $n$，求序列 $s$ 的第 $n$ 个元素。

你需要回答 $t$ 个相互独立的测试用例。

序列 $a$ 字典序小于序列 $b$，当且仅当在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 在该位置的元素小于 $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.

第一行包含一个整数 $t$（$1 \le t \le 10^5$）—— 测试用例的数量。

接下来的 $t$ 行中，每行包含一个整数 $n$（$1\le n \le 10^{16}$）—— 你要查询的元素的位置。

In each of the $t$ lines, output the answer to the corresponding test case.

在每行的 $t$ 行中，输出对应测试用例的答案。

The first elements of $s$ are $1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $

序列 $s$ 的前若干项为 $1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $