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.


-----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, \dots $

Difficulty: HARD
Tags: Bit manipulation

Constructive algorithms

Complete search

Divide and conquer

Mathematics
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
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 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 new_find_pair(n):
	stack = []
	while n:
		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) = (0, 0, 0)
	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)

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)


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 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)))


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
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)


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
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))


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
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)


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