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

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Complete search

Divide and conquer

Mathematics
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
memo = [(0, 0, 0)]

def new_find_pair(n):
	stack = []
	while n >= len(memo):
		N = n.bit_length() - 1
		if N % 2 == 0:
			i = N // 2
			stack.append((n, 1, i))
			n -= 4 ** i
		else:
			i = N // 2
			if n >> 2 * i & 1 == 0:
				stack.append((n, 2, i))
				n -= 2 * 4 ** i
			else:
				stack.append((n, 3, i))
				n -= 3 * 4 ** i
	(a, b, c) = memo[n]
	for (m, t, i) in stack[::-1]:
		m -= t * 4 ** i
		if t == 1:
			if m == b:
				(a, b, c) = (b, c, a)
			elif m == c:
				(a, b, c) = (c, a, b)
		elif t == 2:
			if m == a:
				(a, b, c) = (c, a, b)
			elif m == c:
				(a, b, c) = (b, c, a)
		elif m == a:
			(a, b, c) = (b, c, a)
		elif m == b:
			(a, b, c) = (c, a, b)
		a += 4 ** i
		b += 2 * 4 ** i
		c += 3 * 4 ** i
	return (a, b, c)
for i in range(1, 4 ** 5):
	memo.append(new_find_pair(i))

def nth_pair(n):
	tmp = 0
	for i in range(28):
		tmp += 4 ** i
		if tmp >= n:
			tmp -= 4 ** i
			first = n - tmp - 1 + 4 ** i
			return new_find_pair(first)

def nth_seq(n):
	q = (n - 1) // 3 + 1
	fst = (n - 1) % 3
	res = nth_pair(q)[fst]
	return res
import sys
input = sys.stdin.buffer.readline
Q = int(input())
for _ in range(Q):
	n = int(input())
	r = nth_seq(n)
	print(r)


import sys
input = sys.stdin.buffer.readline
for f in range(int(input())):
	n = int(input())
	size = 2
	ma = 4
	while n >= ma:
		ma *= 4
		size += 2
	pr = ma // 4
	ind = n - pr
	ind //= 3
	first = [0] * size
	first[1] = 1
	i = size - 1
	while ind > 0:
		if ind % 2 == 1:
			first[i] = 1
		ind //= 2
		i -= 1
	if n % 3 == 1:
		s = 0
		for i in range(size):
			s *= 2
			if first[i] == 1:
				s += 1
		print(s)
	if n % 3 == 2:
		for i in range(size // 2):
			if first[2 * i] == 0 and first[2 * i + 1] == 1:
				first[2 * i] = 1
				first[2 * i + 1] = 0
			elif first[2 * i] == 1 and first[2 * i + 1] == 0:
				first[2 * i] = 1
				first[2 * i + 1] = 1
			elif first[2 * i] == 1 and first[2 * i + 1] == 1:
				first[2 * i] = 0
				first[2 * i + 1] = 1
		s = 0
		for i in range(size):
			s *= 2
			if first[i] == 1:
				s += 1
		print(s)
	if n % 3 == 0:
		for i in range(size // 2):
			if first[2 * i] == 0 and first[2 * i + 1] == 1:
				first[2 * i] = 1
				first[2 * i + 1] = 1
			elif first[2 * i] == 1 and first[2 * i + 1] == 0:
				first[2 * i] = 0
				first[2 * i + 1] = 1
			elif first[2 * i] == 1 and first[2 * i + 1] == 1:
				first[2 * i] = 1
				first[2 * i + 1] = 0
		s = 0
		for i in range(size):
			s *= 2
			if first[i] == 1:
				s += 1
		print(s)


import os
import sys
from io import BytesIO, IOBase

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))

def main():
	dc = {'11': ['01', '10'], '10': ['11', '01'], '01': ['10', '11'], '00': ['00', '00']}
	T = iin()
	while T:
		T -= 1
		n = iin() - 1
		ch1 = n % 3
		x = n // 3
		ch = 0
		while x >= 1 << ch:
			x -= 1 << ch
			ch += 2
		a1 = (1 << ch) + x
		a1 = '0' + bin(a1)[2:]
		l = len(a1)
		a2 = []
		a3 = []
		i = l - 1
		while i >= 0:
			if i > 0:
				x3 = a1[i - 1] + a1[i]
				(x1, x2) = dc[x3]
				a2.append(x1)
				a3.append(x2)
				i -= 2
			else:
				i -= 1
		a2 = ''.join(a2[::-1])
		a3 = ''.join(a3[::-1])
		a = [int(a1, 2), int(a2, 2), int(a3, 2)]
		print(a[ch1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = sys.stdin.readline
Q = int(input())
Query = [int(input()) for _ in range(Q)]
for N in Query:
	N -= 1
	seq = N // 3
	where = N % 3
	T = 0
	for l in range(100):
		a = 4 ** l
		if T + a > seq:
			start = seq - T + a
			break
		T += a
	if where == 0:
		print(start)
	else:
		b = start - a
		b_str = bin(b)[2:]
		b_str = '0' * (a.bit_length() - 1 - len(b_str)) + b_str
		L = len(b_str) // 2
		p_str = ''
		for l in range(L):
			tmp = b_str[2 * l:2 * l + 2]
			if tmp == '00':
				p_str += '00'
			elif tmp == '01':
				p_str += '10'
			elif tmp == '10':
				p_str += '11'
			else:
				p_str += '01'
		second = int('10' + p_str, 2)
		if where == 1:
			print(second)
		else:
			print(start ^ second)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	(q, r) = ((n - 1) // 3, n % 3)
	i = 0
	while q >= 1 << (i << 1):
		q -= 1 << (i << 1)
		i += 1
	quad = [0] * i
	if r == 1:
		s = 0
		while q > 0:
			quad[s] += q % 4
			q >>= 2
			s += 1
		res = 1 << len(quad) * 2
		for (j, x) in enumerate(quad):
			res += {0: 0, 1: 1, 2: 2, 3: 3}[x] << j * 2
		print(res)
		continue
	if r == 2:
		s = 0
		while q > 0:
			quad[s] += q % 4
			q >>= 2
			s += 1
		res = 2 << len(quad) * 2
		for (j, x) in enumerate(quad):
			res += {0: 0, 1: 2, 2: 3, 3: 1}[x] << j * 2
		print(res)
		continue
	if r == 0:
		s = 0
		while q > 0:
			quad[s] += q % 4
			q >>= 2
			s += 1
		res = 3 << len(quad) * 2
		for (j, x) in enumerate(quad):
			res += {0: 0, 1: 3, 2: 1, 3: 2}[x] << j * 2
		print(res)
		continue


import os
import sys
from io import BytesIO, IOBase

def main():
	T = int(input())
	for case_idx in range(1, T + 1):
		ans = solve_case()
		print('{}'.format(ans))
bit_pair_cycle_3 = ['01', '10', '11']
bit_pair_cycle_4_3 = [['00', '00', '00'], ['01', '10', '11'], ['10', '11', '01'], ['11', '01', '10']]

def solve_case():
	n = int(input())
	if n <= 3:
		return n
	bin_n = bin(n)[2:]
	using_bit_pair_count = (len(bin_n) + 1) // 2
	inside_idx = n - 4 ** (using_bit_pair_count - 1)
	ans_bit_pairs = [None] * using_bit_pair_count
	for bit_pair_idx in range(using_bit_pair_count):
		if bit_pair_idx == using_bit_pair_count - 1:
			bit_pair = bit_pair_cycle_3[inside_idx % 3]
		else:
			triple_idx = inside_idx // 3
			in_triple_idx = inside_idx % 3
			cycle_4_idx = triple_idx // 4 ** bit_pair_idx % 4
			bit_pair = bit_pair_cycle_4_3[cycle_4_idx][in_triple_idx]
		ans_bit_pairs[bit_pair_idx] = bit_pair
	bin_ans = ''.join(reversed(ans_bit_pairs))
	ans = int(bin_ans, 2)
	return ans
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		N = int(input())
		if N <= 3:
			print(N)
			continue
		if N % 3 == 1:
			k = N.bit_length() - 1
			if k & 1:
				k -= 1
			print(2 ** k + (N - 2 ** k) // 3)
		elif N % 3 == 2:
			N1 = N - 1
			k = N1.bit_length() - 1
			if k & 1:
				k -= 1
			ans1 = 2 ** k + (N1 - 2 ** k) // 3
			ans = 0
			cnt = 0
			while ans1:
				a = ans1 % 4
				if a == 1:
					a = 2
				elif a == 2:
					a = 3
				elif a == 3:
					a = 1
				ans += a * 4 ** cnt
				cnt += 1
				ans1 >>= 2
			print(ans)
		else:
			N1 = N - 2
			k = N1.bit_length() - 1
			if k & 1:
				k -= 1
			ans1 = 2 ** k + (N1 - 2 ** k) // 3
			ans = 0
			cnt = 0
			while ans1:
				a = ans1 % 4
				if a == 1:
					a = 3
				elif a == 2:
					a = 1
				elif a == 3:
					a = 2
				ans += a * 4 ** cnt
				cnt += 1
				ans1 >>= 2
			print(ans)
main()


import sys
input = sys.stdin.readline
import bisect
L = [4 ** i for i in range(30)]

def calc(x):
	fami = bisect.bisect_right(L, x) - 1
	base = (x - L[fami]) // 3
	cl = x % 3
	if cl == 1:
		return L[fami] + base
	else:
		cl1 = L[fami] + base
		ANS = 0
		for i in range(30):
			x = cl1 // L[i] % 4
			if x == 1:
				ANS += 2 * L[i]
			elif x == 2:
				ANS += 3 * L[i]
			elif x == 3:
				ANS += L[i]
		if cl == 2:
			return ANS
		else:
			return ANS ^ cl1
t = int(input())
for tests in range(t):
	print(calc(int(input())))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
from collections import deque

def main():
	t = int(input())
	Block = [['00', '01', '10', '11'], ['00', '10', '11', '01'], ['00', '11', '01', '10']]
	for _ in range(t):
		n = int(input()) - 1
		idx = n % 3
		prefix = Block[idx][1]
		ans = deque()
		cycle_idx = n // 3 - 1
		while cycle_idx >= 0:
			ans.appendleft(Block[idx][cycle_idx % 4])
			cycle_idx //= 4
			cycle_idx -= 1
		ans.appendleft(prefix)
		sys.stdout.write(str(int(''.join(ans), 2)) + '\n')
main()


from math import *
from sys import stdin, stdout
MAXR = 64

class ba:
	u = 0
	v = 0

def getBool(z):
	ans = ba()
	if z == 0:
		ans.u = '0'
		ans.v = '0'
	elif z == 1:
		ans.u = '0'
		ans.v = '1'
	elif z == 2:
		ans.u = '1'
		ans.v = '0'
	else:
		ans.u = '1'
		ans.v = '1'
	return ans

def getInt(u, v):
	if u == '0' and v == '0':
		return 0
	elif u == '0' and v == '1':
		return 1
	elif u == '1' and v == '0':
		return 2
	else:
		return 3
x = [[0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
t = int(stdin.readline())
for w in range(t):
	a = int(stdin.readline())
	q = int(log(a, 4))
	q = int(pow(4, q))
	d = int(a - q)
	f = int(d % 3)
	ques = int(q + int(d / 3))
	ans = ['0' for i in range(MAXR)]
	qu = list(bin(ques)[2:].zfill(MAXR))
	for i in range(0, MAXR, 2):
		l = getInt(qu[i], qu[i + 1])
		e = x[f][l]
		y = getBool(e)
		ans[i] = y.u
		ans[i + 1] = y.v
	ans = str(int('0b' + ''.join(ans), 2)) + '\n'
	stdout.write(ans)


from sys import stdin
input = stdin.readline
pot = [1] * 40
for i in range(1, 40):
	pot[i] = 4 * pot[i - 1]
poczatki = [1, 2]
for i in range(38):
	os = poczatki[-1]
	poczatki.append(os + pot[i + 1])
tab = [[0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]

def odp(ind, m3):
	if ind == 1:
		return m3 + 1
	else:
		m = ind
		while m % 4 != 2:
			m -= 1
		i = 0
		while poczatki[i + 1] <= m:
			i += 1
		miejsce = (m - poczatki[i]) // 4
		pre = poczatki[i - 1] + miejsce
		return 4 * odp(pre, m3) + tab[m3][ind - m]
t = int(input())
for _ in range(t):
	n = int(input())
	a = (n - 1) % 3
	b = (n - 1) // 3 + 1
	print(odp(b, a))


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
T = int(input())
for _ in range(T):
	N = int(input())
	(i, m) = divmod(N - 1, 3)
	s = 0
	for d in range(100):
		s += 4 ** d
		if s > i:
			s -= 4 ** d
			break
	a = 1 << d * 2
	l = i - s
	a += l
	b = 1 << d * 2 + 1
	for bit in range(0, 80, 2):
		b |= [0, 2, 3, 1][l >> bit & 3] << bit
	c = a ^ b
	print([a, b, c][m])


import sys
input = sys.stdin.readline
from itertools import combinations
t = int(input())
for tt in range(t):
	n = int(input()) - 1
	mod3 = n % 3
	n = n // 3
	i = 0
	while n >= 4 ** i:
		n -= 4 ** i
		i += 1
	if i == 0:
		a = 1
		b = 2
		c = 3
	else:
		a = 4 ** i + n
		left = 0
		right = 4 ** i
		b = 4 ** i * 2
		t = n
		while right - left > 1:
			mid1 = (left * 3 + right) // 4
			mid2 = (left * 2 + right * 2) // 4
			mid3 = (left + right * 3) // 4
			rng = right - left
			if left <= t < mid1:
				b += 0
			elif mid1 <= t < mid2:
				b += rng // 4 * 2
			elif mid2 <= t < mid3:
				b += rng // 4 * 3
			else:
				b += rng // 4 * 1
			t %= rng // 4
			right //= 4
		c = a ^ b
	if mod3 == 0:
		print(a)
	elif mod3 == 1:
		print(b)
	else:
		print(c)


import sys
lines = sys.stdin.readlines()
t = int(lines[0].strip())
pows = [4 ** i for i in range(64)]
vals = ((0, 1, 2, 3), (0, 2, 3, 1), (0, 3, 1, 2))
prt = []
for iter in range(t):
	n = int(lines[iter + 1].strip())
	pow = 0
	for i in range(64):
		if pows[i + 1] > n:
			pow = i
			break
	n -= pows[pow]
	front = n % 3
	n = n // 3
	ret = (front + 1) * pows[pow]
	for i in range(pow):
		v = vals[front][n % 4]
		ret += v * pows[i]
		n = n // 4
	if iter == 0:
		prt += [str(ret)]
	else:
		prt += ['\n' + str(ret)]
print(''.join(prt))


from collections import defaultdict
from queue import deque
from sys import stdin, stdout
from math import log2

def arrinp():
	return [*map(int, stdin.readline().split(' '))]

def mulinp():
	return map(int, stdin.readline().split(' '))

def intinp():
	return int(stdin.readline())

def solution():
	n = intinp()
	if n <= 3:
		print(n)
		return
	if n % 3 == 1:
		k = n.bit_length() - 1
		if k & 1:
			k -= 1
		print(2 ** k + (n - 2 ** k) // 3)
	elif n % 3 == 2:
		n1 = n - 1
		k = n1.bit_length() - 1
		if k & 1:
			k -= 1
		ans1 = 2 ** k + (n1 - 2 ** k) // 3
		ans = 0
		cnt = 0
		while ans1:
			a = ans1 % 4
			if a == 1:
				a = 2
			elif a == 2:
				a = 3
			elif a == 3:
				a = 1
			ans += a * 4 ** cnt
			cnt += 1
			ans1 >>= 2
		print(ans)
	else:
		n1 = n - 2
		k = n1.bit_length() - 1
		if k & 1:
			k -= 1
		ans1 = 2 ** k + (n1 - 2 ** k) // 3
		ans = 0
		cnt = 0
		while ans1:
			a = ans1 % 4
			if a == 1:
				a = 3
			elif a == 2:
				a = 1
			elif a == 3:
				a = 2
			ans += a * 4 ** cnt
			cnt += 1
			ans1 >>= 2
		print(ans)
testcases = 1
testcases = intinp()
for _ in range(testcases):
	solution()


import sys

def input():
	return sys.stdin.readline()[:-1]
t = int(input())
rep = [[0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
pows = [1 for _ in range(30)]
for i in range(1, 30):
	pows[i] = pows[i - 1] * 4
for _ in range(t):
	n = int(input())
	n -= 1
	(quo, mod) = (n // 3, n % 3)
	(stage, cum) = (0, 0)
	while cum + pows[stage] <= quo:
		cum += pows[stage]
		stage += 1
	quo -= cum
	ans = pows[stage] * rep[mod][1]
	for k in range(stage):
		ans += pows[k] * rep[mod][quo % 4]
		quo //= 4
	print(ans)


import sys
lines = sys.stdin.readlines()
T = int(lines[0].strip())
partial = [1, 2, 3, 4, 8, 12, 5, 10, 15, 6, 11, 13, 7, 9, 14, 16, 32, 48, 17, 34, 51, 18, 35, 49, 19, 33, 50, 20, 40, 60, 21, 42, 63, 22, 43, 61, 23, 41, 62, 24, 44, 52, 25, 46, 55, 26, 47, 53, 27, 45, 54, 28, 36, 56, 29, 38, 59, 30, 39, 57, 31, 37, 58, 64, 128, 192, 65, 130, 195, 66, 131, 193, 67, 129, 194, 68, 136, 204, 69, 138, 207, 70, 139, 205, 71, 137, 206, 72, 140, 196, 73, 142, 199, 74, 143, 197, 75, 141, 198, 76, 132, 200, 77, 134, 203, 78, 135, 201, 79, 133, 202, 80, 160, 240, 81, 162, 243, 82, 163, 241, 83, 161, 242, 84, 168, 252, 85, 170, 255, 86, 171, 253, 87, 169, 254, 88, 172, 244, 89, 174, 247, 90, 175, 245, 91, 173, 246, 92, 164, 248, 93, 166, 251, 94, 167, 249, 95, 165, 250, 96, 176, 208, 97, 178, 211, 98, 179, 209, 99, 177, 210, 100, 184, 220, 101, 186, 223, 102, 187, 221, 103, 185, 222, 104, 188, 212, 105, 190, 215, 106, 191, 213, 107, 189, 214, 108, 180, 216, 109, 182, 219, 110, 183, 217, 111, 181, 218, 112, 144, 224, 113, 146, 227, 114, 147, 225, 115, 145, 226, 116, 152, 236, 117, 154, 239, 118, 155, 237, 119, 153, 238, 120, 156, 228, 121, 158, 231, 122, 159, 229, 123, 157, 230, 124, 148, 232, 125, 150, 235, 126, 151, 233, 127, 149, 234, 256, 512, 768]
for t in range(T):
	n = int(lines[t + 1].strip())
	if n <= 255:
		print(partial[n - 1])
		continue
	index = n % 3
	lowPow4 = 4 ** (len(bin(n)[3:]) // 2)
	first = lowPow4 + (n - lowPow4) // 3
	tmp = [0, 2, 3, 1]

	def theSecond(fi):
		if fi < 128:
			j = partial.index(fi)
			return partial[j + 1]
		prev = theSecond(fi // 4)
		return prev * 4 + tmp[fi % 4]
	second = theSecond(first)
	if index == 1:
		print(first)
	elif index == 2:
		print(second)
	else:
		print(first ^ second)


import io
import os
from collections import Counter, defaultdict, deque
DEBUG = False

def solve(N):
	if DEBUG:
		ans = []
		S = set()
		M = 100
		for a in range(1, M):
			if a not in S:
				for b in range(1, 10 ** 100):
					if b not in S:
						c = a ^ b
						if a != b and b != c and (a != c) and (a not in S) and (b not in S) and (c not in S):
							S.add(a)
							S.add(b)
							S.add(c)
							ans.append(a)
							ans.append(b)
							ans.append(c)
							if True:
								print(bin(a)[2:].rjust(30), bin(b)[2:].rjust(30), bin(c)[2:].rjust(30), '\t', a, b, c)
							break
	if N <= 3:
		return N
	else:
		p = 1
		tripletIndex = (N - 1) // 3
		offset = tripletIndex
		while offset >= p:
			offset -= p
			p *= 4
		a = p + offset
		aBin = bin(a)[2:]
		if len(aBin) % 2:
			aBin = '0' + aBin
		mapping = {'01': '10', '11': '01', '10': '11', '00': '00'}
		bBin = []
		for i in range(0, len(aBin), 2):
			bBin.append(mapping[aBin[i:i + 2]])
		b = int(''.join(bBin), base=2)
		c = a ^ b
		ret = [a, b, c][(N - 1) % 3]
		if DEBUG:
			assert ans[N - 1] == ret
		return ret
if DEBUG:
	for i in range(1, 100):
		solve(i)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N,) = [int(x) for x in input().split()]
	ans = solve(N)
	print(ans)


from bisect import bisect
subst = [0, 2, 3, 1]
pows = [4 ** i for i in range(28)]

def nxt(x):
	temp = []
	while x:
		temp.append(x % 4)
		x //= 4
	res = 0
	for v in temp[::-1]:
		res = res * 4 + subst[v]
	return res

def task(x):
	y = x - (x - 1) % 3
	r = pows[bisect(pows, y) - 1]
	z = y - (y - r) // 3 * 2
	for _ in range(x - y):
		z = nxt(z)
	return z
for _ in range(int(input())):
	print(task(int(input())))


import os
import sys
input = sys.stdin.buffer.readline
from collections import deque
from queue import PriorityQueue
import math

class CF(object):

	def __init__(self):
		self.g = []
		for i in range(100):
			self.g.append(4 ** i * 3)

	def gao(self, x, n):
		re = deque()
		rest = x % 3
		cnt = int(x // 3)
		for i in range(n):
			re.appendleft(cnt % 4)
			cnt = int(cnt // 4)
		pass
		ans = rest + 1
		for i in range(n):
			ans <<= 2
			if re[i] == 1:
				ans += rest + 1
			elif re[i] == 2:
				if rest == 0:
					ans += 2
				elif rest == 1:
					ans += 3
				elif rest == 2:
					ans += 1
			elif re[i] == 3:
				if rest == 0:
					ans += 3
				elif rest == 1:
					ans += 1
				elif rest == 2:
					ans += 2
		pass
		print(ans)

	def main(self):
		self.t = int(input())
		for _ in range(self.t):
			pos = int(input())
			now = 0
			while True:
				if pos > self.g[now]:
					pos -= self.g[now]
					now += 1
				else:
					break
			pass
			x = pos - 1
			self.gao(x, now)
		pass
cf = CF()
cf.main()
pass


def log4(n):
	k = 0
	while n > 3:
		n //= 4
		k += 1
	return k

def manual_test(n):
	a = 0
	s = []
	forbidden = set()
	while len(s) < n:
		a = a + 1
		while a in forbidden:
			a += 1
		b = a + 1
		while b in forbidden or a ^ b in forbidden or a ^ b < b:
			b += 1
		s.append((a, b, a ^ b))
		forbidden.add(a)
		forbidden.add(b)
		forbidden.add(a ^ b)
	for (i, x) in enumerate(s):
		print('{:3d} {}'.format(i + 1, x))
		y = abc(i + 1)
		assert x == y, y
	exit(0)
	return

def f(x, y):
	if y == 0:
		return 0
	(q, r) = divmod(x, y)
	return [0, 2, 3, 1][q] * y + f(r, y // 4)

def abc(n):
	if n == 1:
		(a, b) = (1, 2)
	else:
		m = n * 3 - 2
		x = 4 ** log4(m)
		d = (m - x) // 3
		(a, b) = (x + d, 2 * x + f(d, x // 4))
	return (a, b, a ^ b)
import sys
ints = (int(s) for s in sys.stdin.read().split())
ntc = next(ints)
ans = []
for tc in range(1, 1 + ntc):
	n = next(ints)
	(n, r) = divmod(n + 2, 3)
	ans.append(abc(n)[r])
print('\n'.join(map(str, ans)))


from bisect import bisect, bisect_left
from collections import *
from heapq import *
from math import gcd, ceil, sqrt, floor, inf
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] > self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

class UF:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n
		self.size = AI(n, 1)
		self.edge = A(n)

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			self.edge[pu] += 1
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			self.edge[pu] += self.edge[pv] + 1
			self.size[pu] += self.size[pv]
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv
			self.edge[pv] += self.edge[pu] + 1
			self.size[pv] += self.size[pu]

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return flag

def dij(s, graph):
	d = AI(n, inf)
	d[s] = 0
	heap = [(0, s)]
	vis = A(n)
	while heap:
		(dis, u) = heappop(heap)
		if vis[u]:
			continue
		vis[u] = 1
		for (v, w) in graph[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

def michange(a, b):
	d = defaultdict(deque)
	for (i, x) in enumerate(b):
		d[x].append(i)
	order = A(len(a))
	for (i, x) in enumerate(a):
		if not d:
			return -1
		order[i] = d[x].popleft()
	return RP(order)

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None

@bootstrap
def dfs(r, p):
	par[r] = p
	for ch in g[r]:
		if ch != p:
			dep[ch] = dep[r] + 1
			yield dfs(ch, r)
	yield None
t = N()
for i in range(t):
	n = N()
	k = 1
	while k <= n:
		k *= 4
	k >>= 2
	if k == n:
		ans = n
	else:
		q = n - k
		if q % 3 == 0:
			ans = q // 3 + k
		elif q % 3 == 1:
			g = q // 3
			mul = 1
			ans = k * 2
			d = [0, 2, 3, 1]
			while g:
				(g, m) = divmod(g, 4)
				ans += d[m] * mul
				mul *= 4
		else:
			ans = k * 3
			g = q // 3
			mul = 1
			d = [0, 3, 1, 2]
			while g:
				(g, m) = divmod(g, 4)
				ans += d[m] * mul
				mul *= 4
	print(ans)


tail = [['00', '00', '00'], ['01', '10', '11'], ['10', '11', '01'], ['11', '01', '10']]
top = ['01', '10', '11']
S = []
E = []
cur = 1
for i in range(32):
	S.append(cur)
	E.append(4 * cur - 1)
	cur *= 4

def convert(s):
	cur = 1
	ans = 0
	for x in s[::-1]:
		if x == '1':
			ans |= cur
		cur <<= 1
	return ans

def solve(n):
	i = 0
	while n > E[i]:
		i += 1
	remain = n - S[i]
	(d, r) = (remain // 3, remain % 3)
	ans = []
	for _ in range(i):
		ans.append(tail[d % 4][r])
		d //= 4
	ans.append(top[(n - 1) % 3])
	return convert(''.join(ans[::-1]))
print('\n'.join([str(solve(int(input()))) for _ in range(int(input()))]))


from collections import deque
import sys
input = sys.stdin.readline
t = int(input())
a = [['00', '01', '10', '11'], ['00', '10', '11', '01'], ['00', '11', '01', '10']]
for _ in range(t):
	n = int(input()) - 1
	m = n % 3
	prefix = a[m][1]
	ans = deque()
	n = n // 3 - 1
	e = 1
	while n >= 0:
		ans.appendleft(a[m][n % 4])
		n = (n >> 2) - 1
	ans.appendleft(prefix)
	sys.stdout.write(str(int(''.join(ans), 2)) + '\n')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	n = int(input())

	def f1(x, pow=1):
		if x > 4 ** pow:
			return f1(x - 4 ** pow, pow + 1)
		return 4 ** pow + (x - 1)

	def f2(x, pow=1):
		if x > 4 ** pow:
			return f2(x - 4 ** pow, pow + 1)
		alpha = 2 * 4 ** pow
		while x > 4:
			rem = (x - 1) // 4 ** (pow - 1)
			alpha += 4 ** (pow - 1) * [0, 2, 3, 1][rem]
			x -= 4 ** (pow - 1) * rem
			pow -= 1
		return alpha + [0, 2, 3, 1][x - 1]
	if n <= 3:
		print(n)
		continue
	if n % 3 == 1:
		n //= 3
		print(f1(n))
	elif n % 3 == 2:
		n //= 3
		print(f2(n))
	elif n % 3 == 0:
		n //= 3
		n -= 1
		print(f1(n) ^ f2(n))


import sys
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
	n = int(input())
	n -= 1
	rem = n % 3
	n //= 3
	s = []
	if n:
		n -= 1
		while n >= 0:
			s.append([['00', '00', '00'], ['01', '10', '11'], ['10', '11', '01'], ['11', '01', '10']][n % 4][rem])
			n //= 4
			n -= 1
	s.append(['1', '10', '11'][rem])
	s.reverse()
	out.append(int(''.join(s), 2))
print('\n'.join(map(str, out)))


import sys
input = sys.stdin.readline
t = int(input())
s = [int(input()) for i in range(t)]
res = []
for num in s:
	num -= 1
	mod = num % 3
	num = num // 3
	div = 1
	while True:
		if num // div != 0:
			num -= div
			div *= 4
		else:
			break
	a = div + num
	b = a * 2
	tmp = a
	coff = 1
	while True:
		if tmp == 0:
			break
		if tmp % 4 == 2:
			b -= coff
		if tmp % 4 == 3:
			b -= coff * 5
		tmp = tmp // 4
		coff *= 4
	c = a ^ b
	if mod == 0:
		print(a)
	if mod == 1:
		print(b)
	if mod == 2:
		print(c)


def find_answer(n):
	(trio_num, trio_place) = (n // 3, n % 3)
	digit = 1
	while trio_num >= 0:
		trio_num -= digit
		digit *= 4
	digit //= 4
	trio_num += digit
	t1 = digit + trio_num
	if trio_place == 0:
		return t1
	(t2, t3) = (digit * 2, digit * 3)
	new_digit = 1
	while new_digit < digit:
		x = t1 % 4
		if x == 1:
			t2 += new_digit * 2
			t3 += new_digit * 3
		elif x == 2:
			t2 += new_digit * 3
			t3 += new_digit * 1
		elif x == 3:
			t2 += new_digit * 1
			t3 += new_digit * 2
		t1 //= 4
		new_digit *= 4
	return t2 if trio_place == 1 else t3
n = int(input())
ans = []
for i in range(n):
	x = int(input())
	ans += [find_answer(x - 1)]
for x in ans:
	print(x)


import os
import sys
mapper = {'00': '00', '01': '10', '10': '11', '11': '01'}

def f(n):
	n1 = (n - 1) // 3
	if n1 >= 1466015503701:
		x = 1466015503701
		i = 21
	else:
		x = 0
		i = 0
	while n1 >= x + 4 ** i:
		x += 4 ** i
		i += 1
	t1 = 4 ** i + n1 - x
	t2 = int('10' + ''.join((mapper[bin(t1)[3:][2 * j:2 * (j + 1)]] for j in range(i))), 2)
	idx = n - n1 * 3 - 1
	if idx == 0:
		return t1
	elif idx == 1:
		return t2
	elif idx == 2:
		return t1 ^ t2
	else:
		raise Exception('bug')

def pp(input):
	T = int(input())
	print('\n'.join(map(str, (f(int(input())) for _ in range(T)))))
if 'paalto' in os.getcwd() and 'pydevconsole' in sys.argv[0]:
	from string_source import string_source
	pp(string_source('9\n1\n2\n3\n4\n5\n6\n7\n8\n9'))
else:
	input = sys.stdin.buffer.readline
	pp(input)
assert f(999999999990000) == 1046445486432677

def x():
	for i in range(100000):
		f(999999999990000 + i)


def level(m):
	l = 0
	while m - (1 << l * 2) >= 0:
		m -= 1 << l * 2
		l += 1
	return (l, m)

def to_bin(l, r):
	ls = []
	for __ in range(l):
		ls.append(r % 4)
		r //= 4
	return ls

def off(b, t):
	magic = [[0, 1, 2, 3], [0, 2, 3, 1], [0, 3, 1, 2]]
	base = 1
	ans = 0
	for d in b:
		ans += base * magic[t][d]
		base *= 4
	return ans

def basic(l, t):
	return 4 ** l * (t + 1)

def get_ans(n):
	(m, t) = divmod(n - 1, 3)
	(l, r) = level(m)
	b = to_bin(l, r)
	o = off(b, t)
	s = basic(l, t)
	return s + o
input = __import__('sys').stdin.readline
T = int(input())
for __ in range(T):
	print(get_ans(int(input())))


import sys
from array import array
import typing as Tp

def input():
	return sys.stdin.buffer.readline().decode('utf-8')

def main():
	t = int(input())
	ans_m = [''] * t
	bottom = [[0, 0, 0], [1, 2, 3], [2, 3, 1], [3, 1, 2]]
	for ti in range(t):
		n = int(input())
		n -= 1
		ans = 0
		(x, shift) = (3, 0)
		while n >= 0:
			if n < x:
				ans += n % 3 + 1 << shift
			else:
				(i, j) = ((n - x) // x % 4, n % 3)
				ans += bottom[i][j] << shift
			n -= x
			x *= 4
			shift += 2
		ans_m[ti] = str(ans)
	sys.stdout.buffer.write(('\n'.join(map(str, ans_m)) + '\n').encode('utf-8'))
main()