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 ⊕ b ⊕ c = 0, where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 
    * 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.

Input

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

Each of the next t lines contains a single integer n (1≤ n ≤ 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.

Example

Input


9
1
2
3
4
5
6
7
8
9


Output


1
2
3
4
8
12
5
10
15

Note

The first elements of s are 1, 2, 3, 4, 8, 12, 5, 10, 15, ... 
from __future__ import division,print_function
#from sortedcontainers import SortedList
import sys
#sys.__stdout__.flush()
le = sys.__stdin__.read().split("\n")
l = map(int,le[1:-1])
def f(n):
    if n%3==1:
        n//=3
        po=1
        while n>=po:
            n-=po
            po*=4
        return po+n
    if n%3==2:
        n//=3
        ini=[0,2,3,1]
        po=1
        while n>=po:
            n-=po
            po*=4
        l=[]
        while n:
            l.append(ini[n%4])
            n //= 4
        n=0
        for k in l[::-1]:
            n = 4*n+k
        return 2*po+n
    return f(n-1)^f(n-2)
if False:
    af = []
    m = max(l)
    a=1
    se = set()
    r = []
    def bour():
        global a
        while a in se:
            a += 1
        se.add(a)
        r.append(a)
        for b in range(a,10**12):
            if not(b in se) and not(a^b in se):
                se.add(b)
                r.append(b)
                se.add(a^b)
                r.append(a^b)
                a += 1
                return None
    m=50
    for k in range((m+2)//3):
        bour()
    q=r[1::3]
    print(q)
    """po=1
    z=[]
    while q:
        z.append(q[:po])
        q = q[po:]
        po *= 4
    z=[q[::4] for q in z]
    for q in z:
        print([(bin(a)[2:],bin(b)[4:]) for a,b in enumerate(q)])"""
print("\n".join(map(str,map(f,l))))
