Koga and Ryuho, new generation Athena's saints, are training to improve their control over the cosmos. According to the ancient Masters, a saint's power to control the cosmos strengthens, when one allows the energy of the universe to flow within the body and then concentrates it. This energy can even be used to explode the objects. 

Today's training is based on a game, and the goal is to use as little cosmos as possible to win. Two saints play as follows: 

Initially there are $N$ piles of stones; pile $\mbox{1}$ has $\mbox{1}$ stone, pile $2$ has $2$ stones, and so on. Thus, the $i^{\mbox{th}}$ pile has $\boldsymbol{i}$ stones. The saints take turns and in each turn, a saint must select a non-empty pile and destroy at least half of the stones in it. The winner is the saint who destroys the last available stone . 

For example, from a pile of $7$ stones, a saint must destroy at least $\begin{array}{c}4\end{array}$ stones, leaving a single (and possibly empty) pile at most 3 stones. With such game, saints learn how to use the appropriate amount of cosmos in a single strike: too much will destroy more stones than desired, too little won't be enough. They also improve their battle thinking and strategy skills.

Ryuho suspects that such game is not as random as it appears to be at first glance. He strongly believes that with the correct single blow, you're assured to win from the very first turn, if you play optimally, no matter how good the other saint plays. Moreover, he is particularly interested in knowing the minimum number of stones he needs to destroy at that first move. Can you help him?  

Input Format

First line of the input consists of an integer $\mathbf{T}$, $\mathbf{T}$ testcases follow, each in a new line. Each line will contain a single integer $N$, which describes the number of initial piles as explained above.

Constraints

$1<=T<=10^6$  
$1<=N<=10^9$

Output Format

For each line in the input, output the minimum number of stones Ryuho needs to destroy in his first turn, assuming he starts playing and that both he and Koga play always as well as possible. If this is not possible, just print $\mbox{0}$.

Sample Input 0
5
1
10
6
8
123456

Sample Output 0
1
7
2
7
32768

Explanation 0

For the first testcase, we can see that the saint can destroy the first stone and win the game. 

Sample Input 1
1
3

Sample Output 1
1

Explanation 1

There are three piles with stones $1,2$ and $3$.
Initially Ryuho will remove $\mbox{1}$ stone from the first pile.
Now other saint has $\begin{array}{c}4\end{array}$ options - 

First, to remove all stones from second pile. In that case Ryuho will remove all stones from third pile and win the game.

Second, to remove all stones from third pile. In that case Ryuho will remove all stones from second pile and win the game.

Third, to remove $\mbox{1}$ stone from second pile. In that case Ryuho will remove $2$ stones from third pile and they will be left with $\mbox{1}$ stone in each of the second and third pile. No matter what the other saint selects Ryuho will have an option to select the last stone.

Fourth, to remove $2$ stones from the third pile. In that case Ryuho will remove $\mbox{1}$ stone from second pile and they will be left with $\mbox{1}$ stone in each of the second and third pile. No matter what the other saint selects Ryuho will have an option to select the last stone.

So in all four cases Ryuho will win the game.

Source: hackerrank | Difficulty: MEDIUM
Tags: Game theory


Solutions:
import time
import sys
import itertools
start = time.time()

def f(x):
	if x == 1 or x % 2 == 1:
		return 1
	(p, log) = (1, 1)
	while p * 2 <= x:
		p *= 2
		log += 1
	xor = log ^ 1
	ans = x + 1
	for prev in range(2, log + 1):
		need = prev ^ xor
		if need < prev:
			before = 1 << prev - 1
			after = (1 << need) - 1
			ans = min(ans, max(before - after, before // 2))
	return ans
memo = {1 << x: f(1 << x) for x in itertools.takewhile(lambda x: 1 << x <= 10 ** 9, itertools.count())}
t = int(input())

def g(x):
	if x == 1 or x % 2 == 1:
		return 1
	p2 = 2
	while p2 << 1 <= x:
		p2 <<= 1
	return memo[p2]
for (i, s) in enumerate(sys.stdin):
	print(f(int(s)))
print(time.time() - start, file=sys.stderr)


ans = [None] * 31
for ndig in range(2, 31):
	xors = ndig ^ 1
	k = 2 ** (len(bin(xors)) - 3)
	r = xors - k
	ans[ndig] = 2 ** (k - 1) - 2 ** r + 1 if r != k - 1 else 2 ** (r - 1)

def main(ans=ans):
	ans = [None, None] + ans
	ncases = int(input())
	for _ in range(ncases):
		piles = int(input())
		print(1 if piles & 1 else ans[len(bin(piles))])
main()


import math
import sys
A = [-1] * 34

def getAnswer(i, j):
	if i - j <= 1:
		return 2 ** (i - 2)
	return 2 ** (i - 1) - (2 ** j - 1)
for SG in range(2, 34):
	flag = True
	for i in range(2, SG):
		for j in range(1, i + 1):
			if 1 ^ i - j ^ i ^ SG == 0:
				A[SG] = getAnswer(i, i - j)
				flag = False
				break
		if not flag:
			break
T = int(input())
for line in sys.stdin:
	N = int(line)
	if N % 2 == 1:
		print(1)
	else:
		SG = int(math.log2(N)) + 1
		if A[SG] == -1:
			print(2 ** (SG - 1) - 1)
		else:
			print(A[SG])


import math
results = []

def HelpFunc(i, sgTo):
	fromm = 2 ** (i - 1)
	to = fromm // 2 if i == sgTo + 1 else 2 ** sgTo - 1
	return fromm - to
keys = [(i, j) for i in range(2, 32) for j in range(i)]
table = {key: HelpFunc(*key) for key in keys}
T = int(input())
for t in range(T):
	N = int(input())
	if N % 2:
		results.append(1)
		continue
	sgn = int(math.log(N, 2)) + 1
	result = N + 1
	sgTotal = sgn ^ 1
	for i in range(1, sgn + 1):
		sgTo = sgTotal ^ i
		if i <= sgTo:
			continue
		result = min(result, table[i, sgTo])
		if result == 1:
			break
	results.append(result)
print(*results, sep='\n')


from math import log, floor
DPT = [[0] * i for i in range(33)]
for i in range(1, 33):
	iV = 1 << i - 1
	for j in range(0, i):
		if j == 0:
			DPT[i][j] = iV
		elif j == i - 1:
			DPT[i][j] = iV >> 1
		else:
			DPT[i][j] = iV - ((1 << j) - 1)
T = int(input())
for _ in range(T):
	N = int(input())
	if N == 1 or N == 2:
		print(1)
	elif N % 2 == 1:
		print(1)
	else:
		gN = int(floor(log(N, 2))) + 1
		nimSum = 1 ^ gN
		for i in range(1, gN + 1):
			j = i ^ nimSum
			if j < i:
				print(DPT[i][j])
				break


import math

def next(n):
	return int(math.log(n) / math.log(2) + 1)

def get(n):
	if n == 1:
		return 1
	return 2 ** n - 1
for x in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print(1)
	else:
		grundy = next(n) ^ 1
		pow2 = 2 ** int(math.log(grundy) / math.log(2))
		print(max(2 ** (pow2 - 2), 2 ** (pow2 - 1) - (2 ** (grundy - pow2) - 1)))


def getGrundy(n):
	if n & 1:
		return 1
	i = n.bit_length() - 1
	return i + 2 * (i & 1)
for _ in range(int(input())):
	n = int(input())
	g = getGrundy(n)
	i = 1 << g.bit_length() - 1
	a = 1 << i - 1
	b = 1 << (i ^ g)
	res = a - b + 1
	least = (a >> 1) + (a & 1)
	if res < least:
		print(least)
	else:
		print(res)


from math import log

def G(n):
	if n == 0:
		return 0
	if n % 2 == 1:
		return 1
	exp_2 = int(log(n, 2))
	if exp_2 % 2 == 0:
		return exp_2
	return exp_2 + 2

def get_min_stones(N, nim_value_all_piles, target_pile):
	if N % 2 == 1:
		return 1
	grundy_pile = len(bin(target_pile)[2:])
	grundy_piles_with_one_missing = nim_value_all_piles ^ grundy_pile
	halfway_mark = target_pile // 2
	if grundy_piles_with_one_missing == len(bin(halfway_mark)[2:]):
		return halfway_mark
	else:
		return target_pile - (2 ** grundy_piles_with_one_missing - 1)
for t in range(int(input())):
	N = int(input())
	nim_value_all_piles = G(N)
	exp_2 = int(log(nim_value_all_piles, 2))
	target_pile = 2 ** (2 ** exp_2 - 1)
	print(get_min_stones(N, nim_value_all_piles, target_pile))


import math

def nim(n):
	if n < 3:
		return n
	return int(math.log(n) / math.log(2)) + 1
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 1:
		print(1)
		continue
	else:
		nimber = 1 ^ nim(n)
	pile = pow(2, pow(2, int(math.log(nimber) / math.log(2))) - 1)
	x = nim(pile)
	y = x ^ nimber
	if y == x - 1:
		min_stones = (pile + 1) // 2
	elif y == 0:
		min_stones = pile
	else:
		min_stones = pile - (pow(2, y) - 1)
	print(min_stones)


from math import *
T = int(input())
for i in range(T):
	N = int(input())
	if N % 2 != 0:
		print(1)
	else:
		m = floor(log2(N))
		n = floor(log2(m + 1))
		p = 2 ** n ^ m + 1 ^ 1
		if 2 ** n == p + 1:
			print(2 ** (2 ** n - 2))
		else:
			print(2 ** (2 ** n - 1) - 2 ** p + 1)


def floor_log_2(n):
	log2 = 0
	curr = n
	while curr > 1:
		curr >>= 1
		log2 += 1
	return log2

def solve(n):
	if n % 2 == 1 or n == 2:
		return 1
	log2 = floor_log_2(n)
	ops = 1 + log2
	log_log = floor_log_2(ops)
	if 2 ** (log_log + 1) == ops + 2:
		return 1 << (1 << log_log) - 2
	if ops - 1 > 1 << log_log:
		return (1 << (1 << log_log) - 1) - ((1 << (ops ^ 1 ^ 1 << log_log)) - 1)
	elif ops % 2 == 1:
		return 1 << log2 - 1
	else:
		return (1 << log2) - 1
T = int(input())
for _ in range(T):
	n = int(input())
	print(solve(n))


grundy = [0, 1]
for i in range(1, 6):
	res = 2 ** (2 ** i - 1)
	for j in range(2 ** i):
		if res == 1:
			grundy.append(2 ** (2 ** i - 2))
		else:
			grundy.append(res)
		res -= 2 ** j
for T in range(int(input())):
	N = int(input())
	if N % 2 == 1:
		print(1)
	else:
		print(grundy[len(bin(N)) - 2 ^ 1])


rs = ''

def ml2(n):
	ln = 0
	while n:
		n >>= 1
		ln += 1
	return ln

def sol(n):
	if n & 1:
		return 1
	else:
		ln = ml2(n)
		lln = ml2(ln)
		lle2 = ln - (1 << lln - 1)
		if lle2 == 0:
			return (1 << ln - 1) - 1
		else:
			if lle2 & 1:
				lle2 -= 1
			else:
				lle2 += 1
			t = 0
			s = 1 << (1 << lln - 1) - 1
			if lle2 > 0:
				t = (1 << lle2) - 1
				if t + t > s:
					t = 1 << lle2 - 1
			return s - t
print('\n'.join(map(lambda _: str(sol(int(input()))), range(int(input())))))


def get_floor_deg_2(x, deg_2):
	(start_idx, end_idx) = (0, len(deg_2) - 1)
	while deg_2[end_idx] > x:
		m_idx = (end_idx + start_idx) // 2
		if deg_2[m_idx + 1] > x:
			end_idx = m_idx
		else:
			start_idx = m_idx
	return end_idx
deg_2 = [1]
d = 1
while d <= 1000000000:
	d <<= 1
	deg_2.append(d)
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		print('1')
	else:
		d = get_floor_deg_2(n, deg_2) + 1
		k = deg_2[d - 1]
		m = d ^ 1
		d2 = get_floor_deg_2(m, deg_2) + 1
		k2 = deg_2[d2 - 1]
		if m != k2 and 2 * k2 - m == 1:
			rv = deg_2[k2 - 2]
		else:
			rv = deg_2[k2 - 1] - deg_2[m - k2] + 1
		print(rv)


from math import log2

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(1 + log2(n))
	y = 1 << int(log2(x))
	z = x ^ y
	return 1 << y - 2 if z + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


import os
import sys
from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


import os
import sys
from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


import os
import sys
from math import frexp

def half(n):
	if n % 2 != 0:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1]) - 1
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
a = lambda y: half(y)
test_cases = int(input())
x = [int(input()) for i in range(test_cases)]
for i in x:
	print(half(i))


from math import frexp

def half(n):
	if n % 2 != 0:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1]) - 1
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
a = lambda y: half(y)
test_cases = int(input())
x = [int(input()) for i in range(test_cases)]
for i in x:
	print(a(i))


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


from math import frexp

def half(n):
	if n % 2 != 0:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1]) - 1
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
a = lambda y: half(y)
test_cases = int(input())
x = [int(input()) for i in range(test_cases)]
for i in x:
	print(a(i))


grundy = [0, 1]
for i in range(1, 6):
	res = 2 ** (2 ** i - 1)
	for j in range(2 ** i):
		if res == 1:
			grundy.append(2 ** (2 ** i - 2))
		else:
			grundy.append(res)
		res -= 2 ** j
for T in range(int(input())):
	N = int(input())
	if N % 2 == 1:
		print(1)
	else:
		print(grundy[len(bin(N)) - 2 ^ 1])


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


import time
import sys
import itertools
start = time.time()

def f(x):
	if x == 1 or x % 2 == 1:
		return 1
	(p, log) = (1, 1)
	while p * 2 <= x:
		p *= 2
		log += 1
	xor = log ^ 1
	ans = x + 1
	for prev in range(2, log + 1):
		need = prev ^ xor
		if need < prev:
			before = 1 << prev - 1
			after = (1 << need) - 1
			ans = min(ans, max(before - after, before // 2))
	return ans
memo = {1 << x: f(1 << x) for x in itertools.takewhile(lambda x: 1 << x <= 10 ** 9, itertools.count())}
t = int(input())

def g(x):
	if x == 1 or x % 2 == 1:
		return 1
	p2 = 2
	while p2 << 1 <= x:
		p2 <<= 1
	return memo[p2]
for (i, s) in enumerate(sys.stdin):
	print(f(int(s)))
print(time.time() - start, file=sys.stderr)


ans = [None] * 31
for ndig in range(2, 31):
	xors = ndig ^ 1
	k = 2 ** (len(bin(xors)) - 3)
	r = xors - k
	ans[ndig] = 2 ** (k - 1) - 2 ** r + 1 if r != k - 1 else 2 ** (r - 1)

def main(ans=ans):
	ans = [None, None] + ans
	ncases = int(input())
	for _ in range(ncases):
		piles = int(input())
		print(1 if piles & 1 else ans[len(bin(piles))])
main()


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


import os
import sys
from math import frexp

def solve(n):
	if n & 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
for _ in range(int(input())):
	print(solve(int(input())))


import math
import sys
A = [-1] * 34

def getAnswer(i, j):
	if i - j <= 1:
		return 2 ** (i - 2)
	return 2 ** (i - 1) - (2 ** j - 1)
for SG in range(2, 34):
	flag = True
	for i in range(2, SG):
		for j in range(1, i + 1):
			if 1 ^ i - j ^ i ^ SG == 0:
				A[SG] = getAnswer(i, i - j)
				flag = False
				break
		if not flag:
			break
T = int(input())
for line in sys.stdin:
	N = int(line)
	if N % 2 == 1:
		print(1)
	else:
		SG = int(math.log2(N)) + 1
		if A[SG] == -1:
			print(2 ** (SG - 1) - 1)
		else:
			print(A[SG])


from math import frexp

def half(n):
	if n % 2 != 0:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1]) - 1
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
a = lambda y: half(y)
test_cases = int(input())
x = [int(input()) for i in range(test_cases)]
for i in x:
	print(a(i))


from math import frexp

def half(n):
	if n % 2 == 1:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1] - 1)
	if (x ^ y) + 1 == y:
		return 1 << y - 2
	else:
		return (1 << y - 1) - (1 << (x ^ y)) + 1
a = lambda y: half(y)
test_cases = int(input())
x = [int(input()) for i in range(test_cases)]
for i in x:
	print(a(i))


import os
import sys
from math import frexp

def half(n):
	if n % 2 != 0:
		return 1
	x = 1 ^ int(frexp(n)[1])
	y = 1 << int(frexp(x)[1]) - 1
	return 1 << y - 2 if (x ^ y) + 1 == y else (1 << y - 1) - (1 << (x ^ y)) + 1
a = lambda y: half(y)
test_cases = int(input())
x = [int(input()) for i in range(test_cases)]
for i in x:
	print(a(i))


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()


import sys
from functools import lru_cache

@lru_cache(maxsize=None)
def grundy(n):
	if n == 0:
		return 0
	S = [grundy(m) for m in range(n // 2 + 1)]
	g = 0
	while g in S:
		g += 1
	return g

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		L = N.bit_length()
		G = 1
		if N & 1 == 0:
			G ^= L
		D = 1
		if G != 1:
			GA = 1 << G.bit_length() - 1
			A = 1 << GA - 1
			GB = G ^ GA
			B = min((1 << GB) - 1, A >> 1) if GB else 0
			D = A - B
		sys.stdout.write('%d\n' % D)
main()