考虑正整数的无限序列 $$$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. 返回第一步。
您有整数 $$$n$$$。查找$$$s$$$ 中的第$$$n$$$ 个元素。
您必须回答 $$$t$$$ 独立测试用例。
如果在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小,则序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
接下来的 $$$t$$$ 行都包含一个整数 $$$n$$$ ($$$1\le n \le 10^{16}$$$) — 您想知道的元素的位置。
输出
在每一 $$$t$$$ 行中,输出相应测试用例的答案。
示例
输入 #1
9 1 2 3 4 5 6 7 8 9
输出 #1
1 2 3 4 8 12 5 10 15
注意
$$$s$$$ 的第一个元素是 $$$1, 2, 3, 4, 8, 12, 5, 10, 15, \dots $$$