#P1338C. Perfect Triples

    ID: 3350 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 8 Uploaded By: Tags>bitmasksbrute forceconstructive algorithmsdivide and conquermath*2200

Perfect Triples

Description

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

  1. Find the lexicographically smallest triple of positive integers (a,b,c)(a, b, c) such that
    • abc=0a \oplus b \oplus c = 0, where \oplus denotes the bitwise XOR operation.
    • aa, bb, cc are not in ss.
    Here triple of integers (a1,b1,c1)(a_1, b_1, c_1) is considered to be lexicographically smaller than triple (a2,b2,c2)(a_2, b_2, c_2) if sequence [a1,b1,c1][a_1, b_1, c_1] is lexicographically smaller than sequence [a2,b2,c2][a_2, b_2, c_2].
  2. Append aa, bb, cc to ss in this order.
  3. Go back to the first step.

You have integer nn. Find the nn-th element of ss.

You have to answer tt independent test cases.

A sequence aa is lexicographically smaller than a sequence bb if in the first position where aa and bb differ, the sequence aa has a smaller element than the corresponding element in bb.

The first line contains a single integer tt (1t1051 \le t \le 10^5) — the number of test cases.

Each of the next tt lines contains a single integer nn (1n10161\le n \le 10^{16}) — the position of the element you want to know.

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

Input

The first line contains a single integer tt (1t1051 \le t \le 10^5) — the number of test cases.

Each of the next tt lines contains a single integer nn (1n10161\le n \le 10^{16}) — the position of the element you want to know.

Output

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

Sample Input 1

9
1
2
3
4
5
6
7
8
9

Sample Output 1

1
2
3
4
8
12
5
10
15

Note

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