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$$$.

Input

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.

Output

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

Note

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

Perfect Triples

Examples