Even if it's a really easy question, she won't be able to answer it

— Perfect Memento in Strict Sense

Cirno's perfect bitmasks classroom has just started!

Cirno gave her students a positive integer $x$. As an assignment, her students need to find the minimum positive integer $y$, which satisfies the following two conditions:

$$x\ {and}\ y > 0$$ $$x\ {xor}\ y > 0$$

Where ${and}$ is the bitwise AND operation , and ${xor}$ is the bitwise XOR operation .

Among the students was Mystia, who was truly baffled by all these new operators. Please help her!


-----Input-----

The first line of input contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of input test cases.

For each test case, the only line of input contains one integer $x$ ($1 \leq x \leq 2^{30}$).


-----Output-----

For each test case, print a single integer — the minimum number of $y$.


-----Examples-----

Input
7
1
2
5
9
16
114514
1000000
Output
3
3
1
1
17
2
64


-----Note-----

Test case 1:

$1\; {and}\; 3=1>0$, $1\; {xor}\; 3=2>0$.

Test case 2:

$2\; {and}\; 3=2>0$, $2\; {xor}\; 3=1>0$.

Difficulty: EASY
Tags: Bit manipulation

Complete search
Skill types: Bit manipulation

Complete search

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	x = int(input())
	if x == 1:
		print(3)
	else:
		y = x & -x
		if y == x:
			print(x + 1)
		else:
			print(y)


def main():
	x = int(input())
	if x == 1:
		return 3
	b = bin(x)
	b = b[::-1]
	for i in range(len(b)):
		if b[i] == '1':
			break
	f = pow(2, i)
	if f == x:
		return x + 1
	return f
for _ in range(int(input())):
	print(main())


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	answer = 0
	for i in range(31):
		if n & 1 << i != 0:
			answer = 1 << i
			break
	for i in range(31):
		if answer & n > 0 and answer ^ n > 0:
			break
		else:
			answer = answer | 1 << i
	print(answer)


import sys

def solve_A(number):
	number_orig = number
	result = 1
	while number % 2 == 0:
		number = number // 2
		result *= 2
	if result ^ number_orig == 0:
		return 3 if result == 1 else result + 1
	else:
		return result

def task_A():
	result = []
	count = next(sys.stdin)
	count = int(count.strip())
	for _ in range(count):
		number = next(sys.stdin)
		number = int(number.strip())
		result.append(solve_A(number))
	for r in result:
		print(r)
task_A()


t = int(input())
for j in range(t):
	n = int(input())
	st = bin(n)
	st = '0' + st[2:]
	st = st[::-1]
	i1 = st.find('1')
	i0 = st.find('0')
	if st.count('1') == 1:
		y = 2 ** i1 + 2 ** i0
	else:
		y = 2 ** i1
	print(y)


import math

def solve():
	n = int(input())
	if n == 1:
		print('3')
		return
	if bin(n).count('1') > 1:
		print(1 << int(math.log2(n & -n)))
		return
	print(n + 1)
	return

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


for fix in range(int(input())):
	f = int(input())
	if f == 1 or f == 2:
		print(3)
	elif f % 2 == 1:
		print(1)
	elif f & f - 1 == 0:
		print(f + 1)
	else:
		u = 0
		while True:
			if f & 1 << u > 0:
				print(1 << u)
				break
			u += 1


tcs = int(input())
for tc in range(tcs):
	n = int(input())
	x = list(bin(n)[2:])
	co = x.count('1')
	if n < 3:
		print(3)
	elif co == 1:
		print(n + 1)
	else:
		for i in range(1, n + 1):
			if x[-i] == '1':
				print(pow(2, i - 1))
				break


t = int(input())
for i in range(t):
	x = int(input())
	y = 1 + (x ^ x - 1) >> 1
	if x & y > 0 and x ^ y > 0:
		print(y)
	else:
		j = 2
		p = 0
		while True:
			num = j ** p + y
			if x & num > 0 and x ^ num > 0:
				print(num)
				break
			else:
				p += 1


t = int(input())
while t > 0:
	a = int(input())
	if a % 2 == 0:
		if not a & a - 1:
			print(a + 1)
		else:
			print(a & ~(a - 1))
	elif a > 1:
		print(1)
	else:
		print(3)
	t -= 1


n = int(input())
l = []
for i in range(n):
	t = int(input())
	l.append(t)
for i in l:
	if i == 1:
		print(3)
	elif i % 2 != 0:
		print(1)
	else:
		j = int(i)
		s = 0
		while j % 2 == 0:
			s += 1
			j = j // 2
		if j == 1:
			print(i + 1)
		else:
			print(2 ** s)


from math import pow

def solve():
	n = int(input())
	if n % 2 == 1:
		if n == 1:
			print(3)
		else:
			print(1)
		return
	b = bin(n)[2:]
	if b.count('1') == 1:
		print(n + 1)
		return
	index = 0
	for i in range(len(b)):
		if b[i] == '1':
			index = i
	index = len(b) - 1 - index
	z = int(pow(2, index))
	print(z)
	return
for i in range(int(input())):
	solve()


for i in range(int(input())):
	x = int(input())
	y = x & -x
	while True:
		if x & y > 0 and x ^ y > 0:
			break
		else:
			y += 1
	print(y)


for x in [*map(int, open(0))][1:]:
	b = x & -x
	print(b | (b == x) + (x < 2))


t = int(input())
for i in range(t):
	x = int(input())
	y = x & -x
	while x == y or x & y == 0:
		y += 1
	print(y)


t = int(input())
s = set()
for i in range(32):
	s.add(2 ** i)
for _ in range(t):
	n = int(input())
	if n == 1:
		print(3)
	elif n in s:
		print(n + 1)
	else:
		for i in range(32):
			if 1 << i & n:
				print(1 << i)
				break


for _ in range(int(input())):
	n = int(input())
	s = bin(n)[2:]
	i = s[::-1].index('1')
	j = len(s) - s.index('1') - 1
	if i == j:
		if i == 0:
			ans = 3
		else:
			ans = 2 ** i + 1
	else:
		ans = 2 ** i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	t = bin(n)[2:]
	i = len(t) - 1
	ans = ''
	while i >= 0 and t[i] == '0':
		ans += t[i]
		i -= 1
	ans = '1' + ans
	if n == 1:
		print(3)
	elif i <= 0:
		print(int(ans, 2) + 1)
	else:
		print(int(ans, 2))


for s in [*open(0)][1:]:
	n = int(s)
	if n == 1:
		print(3)
		continue
	a = 1
	while a & n != a:
		a <<= 1
	print(a | (n == a))


testcases = int(input())
for i in range(testcases):
	n = int(input())
	lowestBit = 0
	for i in range(31):
		if n & 1 << i > 0:
			lowestBit = i
			break
	if n & n - 1 > 0:
		print(1 << lowestBit)
	else:
		ans = 1 << lowestBit
		if lowestBit == 0:
			ans = ans | 1 << 1
		else:
			ans = ans | 1 << 0
		print(ans)


import io, os

def ri():
	return int(input().strip())

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

def Solve():
	n = ri()
	cnt = 0
	tn = n
	while tn:
		cnt += tn & 1
		tn >>= 1
	if cnt == 1:
		(x, y) = (0, 0)
		while n >> x & 1 == 0:
			x += 1
		while n >> y & 1 == 1:
			y += 1
		print((1 << x) + (1 << y))
	else:
		x = 0
		while n >> x & 1 == 0:
			x += 1
		print(1 << x)
T = ri()
while T:
	T -= 1
	Solve()


for _ in range(int(input())):
	n = int(input())
	b = list(bin(n)[2:])
	b.reverse()
	if n < 3:
		print(3)
		continue
	if b.count('1') == 1:
		print(n + 1)
		continue
	print(2 ** b.index('1'))


for _ in range(int(input())):
	x = int(input())
	ans = 0
	c1 = c2 = False
	for i in range(32):
		if not c1 and x & 1 << i > 0:
			ans += 1 << i
			c1 = True
	b = bin(x)[2:]
	if b.count('1') == 1:
		if 1 & ans > 0:
			ans += 2
		else:
			ans += 1
	print(ans)


def read_nums():
	return [int(x) for x in input().split()]

def solve():
	(x,) = read_nums()
	bin_x = bin(x)[2:].zfill(32)
	last_set_bit = len(bin_x) - bin_x.rfind('1') - 1
	last_zero = len(bin_x) - bin_x.rfind('0') - 1
	y = 1 << last_set_bit
	if x ^ y == 0:
		y += 1 << last_zero
	return y

def main():
	(t,) = read_nums()
	for _ in range(t):
		print(solve())
main()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(3)
	elif n % 2 == 1:
		print(1)
	else:
		x = int(math.log2(n))
		if 2 ** x == n:
			print(n + 1)
		else:
			while math.log2(n) % 1 != 0:
				n -= 2 ** int(math.log2(n))
			print(n)


from sys import stdin
input = stdin.readline

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))
import math

def Log2(x):
	if x == 0:
		return False
	return math.log10(x) / math.log10(2)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))
for _ in range(ii()):
	n = ii()
	if n == 1:
		print(3)
		continue
	if isPowerOfTwo(n):
		print(n + 1)
		continue
	if n % 2:
		print(1)
	else:
		b = bin(n)[2:][::-1]
		for i in range(len(b)):
			if b[i] == '1':
				pos = i
				break
		print(pow(2, pos))


for _ in range(int(input())):
	x = int(input())
	p = str(bin(x))
	p = p[::-1]
	if p.count('1') == 1:
		k = p.index('1')
		if k == 0:
			y = 2 ** k + 2 ** (k + 1)
		else:
			y = 1 + 2 ** k
	else:
		k = p.index('1')
		y = 2 ** k
	print(y)


import sys
sys.setrecursionlimit(10 ** 5)

def pro(n):
	ans = 0
	for i in range(32):
		if n & 1 << i:
			ans |= 1 << i
			break
	if ans ^ n > 0:
		print(ans)
		return
	for i in range(32):
		if n & 1 << i == 0:
			ans |= 1 << i
			break
	print(ans)
t = int(input())
for i in range(t):
	n = int(input())
	pro(n)


def getOnes(num):
	answer = 0
	while num:
		answer += num & 1
		num >>= 1
	return answer

def getRight(num):
	answer = 1
	while num & 1 == 0:
		answer *= 2
		num >>= 1
	return answer
t = int(input())
while t > 0:
	t -= 1
	x = int(input())
	if getOnes(x) == 1:
		print(max(x + 1, 3))
	else:
		print(getRight(x))


T = int(input())
for testcase in range(T):
	x = int(input())
	b = '0' + bin(x)[2:]
	l = len(b)
	rightmost1 = b.rfind('1')
	rightmost0 = b.rfind('0')
	n = 2 ** (l - rightmost1 - 1)
	if n & x > 0 and n ^ x > 0:
		print(n)
	else:
		n += 2 ** (l - rightmost0 - 1)
		print(n)


import sys
input = lambda : sys.stdin.readline().strip()
for Homu in range(int(input())):
	x = int(input())
	if x % 2 == 1:
		if x ^ 1 > 0:
			print(1)
		else:
			print(3)
	else:
		ans = 1
		x_copy = x
		while x_copy % 2 == 0:
			ans *= 2
			x_copy //= 2
		if x ^ ans > 0:
			print(ans)
		else:
			print(ans + 1)


def solve(x):
	if x == 1:
		return 3
	ans = 1
	while x != 0:
		val = x & 1
		if val:
			if x >> 1 == 0:
				ans += 1
			return ans
		x >>= 1
		ans <<= 1
T = int(input())
for t in range(T):
	x = int(input())
	ans = solve(x)
	print(ans)


t = int(input())
for _ in range(t):
	x = int(input())
	if x == 1:
		print(3)
	elif x % 2 == 1:
		print(1)
	else:
		temp = x
		ans = 1
		while temp:
			curr = temp % 2
			if curr == 1:
				break
			ans *= 2
			temp = temp // 2
		if ans == x:
			print(ans + 1)
		else:
			print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(3)
	else:
		h = bin(n)[2:]
		k = '0' * (len(h) - 1) + '1'
		f = 0
		for i in range(len(h)):
			if h[i] == '1' and h[i] == k[i]:
				f = 1
				break
		if f == 1:
			print(1)
		else:
			idx = -1
			for i in range(len(h) - 1, -1, -1):
				if h[i] == '1':
					idx = i
					break
			k = k[:i] + '1' + k[i + 1:len(k) - 1] + '0'
			ans = int(k, 2)
			if ans == n:
				ans += 1
			print(ans)


t = int(input())
for i in range(t):
	x = int(input())
	copy = x
	count = 0
	while copy % 2 == 0:
		count += 1
		copy /= 2
	if x == 1:
		print(3)
	elif x == 2:
		print(3)
	elif x ^ pow(2, count) > 0:
		print(pow(2, count))
	else:
		print(pow(2, count) + 1)


t = int(input())
for e in range(t):
	n = int(input())
	if n == 1:
		print(3)
	elif n & n - 1 == 0 and n != 0:
		print(n + 1)
	elif n % 2 == 0:
		for i in range(32):
			if n & 1 << i:
				print(2 ** i)
				break
	else:
		print(1)


t = int(input())
for g in range(t):
	n = int(input())
	if n == 1:
		print(3)
	else:
		st = bin(n)[2:]
		ind = st.rfind('1')
		if ind == 0:
			print(n + 1)
		else:
			st1 = '1' + '0' * (len(st) - ind - 1)
			res = int(st1, 2)
			print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	x = int(input())
	bits = []
	for i in range(31):
		if x >> i & 1 == 1:
			bits.append(i)
	y = 1 << bits[0]
	if len(bits) == 1:
		for i in range(31):
			if x >> i & 1 == 0:
				y += 1 << i
				break
	print(y)


for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
		continue
	sx = bin(x)[::-1]
	i = sx.find('1')
	ans = 2 ** i
	print(ans if x > ans else ans + 1)


t = int(input())
ans = list()
for i in range(0, t):
	n = int(input())
	arr = [int(x) for x in bin(n) if x != 'b']
	ans_num = 0
	for k in range(1, len(arr) + 1):
		if arr[-k] == 1:
			ans_num += pow(2, k - 1)
			break
	if ans_num != n:
		ans.append(ans_num)
	else:
		for k in range(1, len(arr) + 1):
			if arr[-k] == 0:
				ans_num += pow(2, k - 1)
				break
		ans.append(ans_num)
for s in ans:
	print(s)


def solve():
	n_decimal = int(input())
	if n_decimal == 1:
		return 3
	counter = 0
	while n_decimal % 2 == 0:
		n_decimal = n_decimal / 2
		counter += 1
	if n_decimal == 1:
		return 2 ** counter + 1
	else:
		return 2 ** counter

def main():
	t = int(input())
	for _ in range(t):
		print(solve())
main()


x = [2]
for i in range(2, 32):
	x.append(pow(2, i))
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
	elif n in x:
		print(n + 1)
	else:
		c = 0
		while n % 2 == 0:
			c += 1
			n /= 2
		print(pow(2, c))


for _ in range(int(input())):
	x = int(input())
	L = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824]
	if x in L:
		if x == 1:
			print(3)
		else:
			print(x + 1)
		continue
	s = bin(x)
	s = s[2:]
	pos = len(s) - s.rfind('1') - 1
	print(2 ** pos)


for _ in range(int(input())):
	n = int(input())
	s = bin(n).replace('0b', '')
	ans = ''
	for i in s[::-1]:
		ans = i + ans
		if i == '1':
			break
	if len(ans) == len(s):
		if ans == '1':
			ans = 3
		else:
			ans = int(ans, 2) + 1
	else:
		ans = int(ans, 2)
	print(ans)


import math

def solve():
	n = int(input())
	bit = int(math.log2(n & -n))
	if n == 1:
		print(3)
	elif 2 ** bit == n:
		print(n + 1)
	else:
		print(2 ** bit)
t = int(input())
while t > 0:
	solve()
	t -= 1


for i in range(int(input())):
	n = int(input())
	binary_form = '0' + bin(n)[2:]
	count_ones = 0
	and_done = 0
	num = ''
	for z in range(len(binary_form) - 1, -1, -1):
		if binary_form[z] == '0' and and_done == 0:
			num = '0' + num
		if binary_form[z] == '1' and and_done == 0:
			and_done = 1
			num = '1' + num
			count_ones += 1
			continue
		elif binary_form[z] == '1':
			count_ones += 1
	if count_ones > 1:
		print(int(num, 2))
	else:
		ind = num.index('1')
		if ind != len(num) - 1:
			print(int(num, 2) + 1)
		else:
			print(3)


def decimalToBinary(n):
	return bin(n).replace('0b', '')
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
	else:
		val = decimalToBinary(n)[::-1]
		one = val.find('1')
		ans = 2 ** one
		if val.count('1') > 1:
			print(ans)
		else:
			zero = val.find('0')
			print(ans + 2 ** zero)


def binary(num):
	return int(bin(num).split('0b')[1])
for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
	elif x % 2 == 1:
		print(1)
	else:
		xb = str(binary(x))
		xb = xb[::-1]
		for i in range(len(xb)):
			if i == len(xb) - 1:
				print(2 ** i + 1)
				break
			elif xb[i] == '1':
				print(2 ** i)
				break


import math
import sys
for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
	elif x % 2 != 0:
		print(1)
	elif x & x - 1 == 0:
		print(x + 1)
	else:
		i = 2
		while True:
			if x & i > 0 and x ^ i > 0:
				print(i)
				break
			i *= 2


for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
	elif n & n - 1 == 0:
		print(n + 1)
	elif n & 1:
		print(1)
	else:
		print(n & ~(n - 1))


for t in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
	else:
		x = bin(x)[2:]
		if x.count('1') > 1:
			i = len(x) - 1
			k = 0
			while x[i] != '1':
				i -= 1
				k += 1
			print(2 ** k)
		else:
			print(2 ** (len(x) - 1) + 1)


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
t = II()

def decimalToBinary(n):
	return '{0:b}'.format(int(n))

def binaryToDecimal(binary):
	binary1 = binary
	(decimal, i, n) = (0, 0, 0)
	while binary != 0:
		dec = binary % 10
		decimal = decimal + dec * pow(2, i)
		binary = binary // 10
		i += 1
	return decimal
for _ in range(t):
	x = II()
	if x == 1:
		print(3)
	else:
		s = decimalToBinary(x)
		last = s.rindex('1')
		if last == 0:
			print(binaryToDecimal(int(s[:-1] + '1')))
		else:
			print(binaryToDecimal(int(s[last:])))


n = int(input())
ans = []
for i in range(n):
	x = int(input())
	if x % 2 and x > 2:
		ans.append(1)
		continue
	if x == 1:
		ans.append(3)
		continue
	k = 1
	while not x >> k & 1:
		k += 1
	if x > 1 << k + 1:
		ans.append(1 << k)
	else:
		ans.append((1 << k) + 1)
for i in ans:
	print(i)


t = int(input())
for _ in range(0, t):
	x = int(input())
	if x % 2 == 1:
		if x > 1:
			print(1)
		else:
			print(3)
	else:
		bin1 = bin(x)[2:]
		str = ''
		flag = 0
		flag2 = 0
		for i in range(len(bin1) - 1, -1, -1):
			if flag == 0 and bin1[i] == '1':
				str = '1' + str
				flag = 1
			elif flag == 1 and bin1[i] == '1':
				flag2 = 1
				break
			elif flag != 1 and bin1[i] == '0':
				str += '0'
		if flag2 == 1:
			print(int(str, 2))
		else:
			print(int(str, 2) + 1)


def solve():
	n = int(input())
	if n == 1:
		print(3)
		return
	f1 = 0
	nc = n
	count = 0
	while nc > 0:
		if nc % 2 == 1:
			break
		count += 1
		nc /= 2
	ans = 2 ** count
	if nc == 1:
		print(ans + 1)
	else:
		print(ans)
t = int(input())
for i in range(t):
	solve()


def solve():
	n = int(input())
	if n == 1:
		return 3
	val = n ^ n - 1
	ans = val ^ val >> 1
	if not n & n - 1:
		ans += 1
	return ans

def main():
	t = int(input())
	for _ in range(t):
		ans = solve()
		print(ans)
main()


for _ in range(int(input())):
	num = bin(int(input()))[2:]
	if num == '1':
		print(3)
		continue
	i = len(num) - 1
	answer = []
	one_flg = False
	zero_flg = False
	while i >= 0:
		if num[i] == '1':
			answer.append('1')
			break
		else:
			answer.append('0')
		i -= 1
	answer.reverse()
	if len(answer) == len(num):
		print(int(''.join(answer), 2) + 1)
	else:
		print(int(''.join(answer), 2))


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
		continue
	x = bin(n)[2:]
	res = 0
	for i in x[::-1]:
		res += 1
		if i == '1':
			break
	res = pow(2, res - 1)
	if x.count('1') == 1:
		res += 1
	print(res)


for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
		continue
	if x % 2:
		print(1)
		continue
	i = 1
	while i <= 30:
		if x & 1 << i:
			break
		i += 1
	ans = 2 ** i
	if ans == x:
		print(2 ** i + 1)
	else:
		print(ans)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
	elif n & 1:
		print(1)
	elif n & n - 1 == 0:
		print(n + 1)
	else:
		val = bin(n)[2:][::-1]
		count = 0
		for i in range(len(val)):
			if val[i] == '1':
				count = i
				break
		val = 2 ** count
		print(val)


for _ in range(int(input())):
	y = int(input())
	y = bin(y)[2:]
	s = ''
	(flag, flag1) = (0, 0)
	e = -1
	for i in range(len(y) - 1, -1, -1):
		if flag == 0:
			if y[i] == '0':
				e = i
				flag = 1
		if y[i] == '0':
			s = '0' + s
		else:
			if i > 0:
				s = '1' + s
			elif flag == 1:
				flag1 = 1
				s = '1' + s
			else:
				s = '11' + s
			break
	if flag1 == 1 and flag == 1:
		s = s[:e] + '1' + s[e + 1:]
	s = int(s, 2)
	print(s)


import sys
ifs = sys.stdin
ofs = sys.stdout

def solve(n):
	b = bin(n)
	b = b[2:]
	pos1 = b.rfind('1')
	min1 = b[pos1:]
	if min1 == '1':
		if len(b) > 1:
			a = '1'
		else:
			a = '11'
	elif '1' in b[:pos1]:
		a = '1' + '0' * (len(b) - pos1 - 1)
	else:
		a = '1' + '0' * (len(b) - pos1 - 2) + '1'
	return int(a, base=2)
T = int(ifs.readline())
for __ in range(T):
	n = int(ifs.readline())
	a = solve(n)
	ofs.write(str(a))
	ofs.write('\n')


t = int(input())
for ii in range(t):
	n = int(input())
	if n == 1:
		print(3)
	elif n % 2 == 1:
		print(1)
	else:
		x = 1
		while n % 2 == 0:
			n = n / 2
			x = x * 2
		if 1 == n:
			print(x + 1)
		else:
			print(x)


for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
		continue
	s = bin(x)[2:]
	ct = 0
	s = s.split('1')
	n = s.__len__()
	if s[-1]:
		print(int('1' + s[-1], 2) + (1 if n == 2 else 0))
	else:
		print(1)


nn = int(input())
while nn != 0:
	n = int(input())
	s = bin(n)
	if s.find('1') == s.rfind('1'):
		print((~n & n + 1) + n)
	else:
		print(n & ~n + 1)
	nn -= 1


t = int(input())
while t:
	n = int(input())
	s = bin(n)[2:]
	s = s[::-1]
	ind = s.index('1')
	if n == 1:
		print(3)
	elif ind == 0:
		print(1)
	elif ind == len(s) - 1:
		print(2 ** ind + 1)
	else:
		print(2 ** ind)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2:
		if n == 1:
			print(3)
		else:
			print(1)
	else:
		a = bin(n)[2:]
		if n & n - 1 == 0:
			print(n + 1)
		else:
			ind = len(a) - 1
			a = str(a)
			for j in range(len(a)):
				if a[j] == '1':
					ans = ind
				ind -= 1
			print(2 ** ans)


def ctz(v):
	return (v & -v).bit_length() - 1

def solve():
	n = int(input())
	if n == 1 or n == 2:
		return 3
	z = ctz(n)
	b = bin(n)
	ones = sum((1 for i in b if i == '1'))
	if ones > 1:
		return 2 ** z
	return n + 1

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


for t in range(int(input())):
	N = int(input())
	if N == 1 or N == 2:
		print(3)
	elif not N & N - 1:
		print(N + 1)
	else:
		c = 0
		while N:
			if N & 1:
				break
			c += 1
			N >>= 1
		print(2 ** c)


for _ in range(int(input())):
	x = int(input())
	last = x & -x
	if last == 1:
		if x ^ last > 0:
			print(1)
		else:
			print(3)
	elif x ^ last > 0:
		print(last)
	else:
		print(last | 1)


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		if not n & n - 1:
			print(n + 1)
		else:
			print(n & ~(n - 1))
	elif n > 1:
		print(1)
	else:
		print(3)


import math
t = int(input())

def decimalToBinary(n):
	return bin(n).replace('0b', '')
i = 1
while i <= t:
	n = int(input())
	if n == 1 or n == 2:
		print(3)
	elif math.ceil(math.log2(n)) == math.log2(n):
		print(n + 1)
	else:
		str = decimalToBinary(n)[::-1]
		index = 0
		while True:
			if str[index] == '1':
				print(int(math.pow(2, index)))
				break
			index = index + 1
	i = i + 1


from random import getrandbits
RANDOM = getrandbits(32)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM
T = int(input())
q = []
for i in range(T):
	n = int(input())
	q.append(n)

def solve(n):
	bits = []
	if n == 1:
		print(3)
		return
	while n > 0:
		bits.append(n % 2)
		n //= 2
	lenn = len(bits)
	j = 0
	while j < lenn and bits[j] != 1:
		j += 1
	ans = 2 ** j
	if j == lenn - 1:
		ans += 1
	print(ans)
for n in q:
	solve(n)


for tc in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		if n & n - 1 == 0:
			print(n + 1)
		else:
			print(n & ~(n - 1))
	elif n > 1:
		print('1')
	else:
		print('3')


t = int(input())
for h in range(t):
	x = int(input())
	if x == 1:
		print(3)
		continue
	k = 0
	g = -1
	l = -1
	while x > 0:
		l += 1
		if x % 2 == 1 and g == -1:
			g = l
		if x % 2 == 1:
			k += 1
		x //= 2
	if k > 1:
		print(2 ** g)
	else:
		print(2 ** g + 1)


t = int(input())
import math
for _ in range(t):
	n = int(input())
	a = 1
	b = 0
	if n % 2 == 0:
		for i in range(1, int(math.log(n, 2)) + 1):
			if n & 1 << i:
				if i != int(math.log(n, 2)):
					print(1 << i)
				else:
					print((1 << i) + 1)
				break
	elif n == 1:
		print(3)
	else:
		print(1)


num = int(input())
while num:
	n = int(input())
	x = bin(n).replace('0b', '')
	y = x.count('1')
	if y == 1 and x == '1':
		print('3')
	elif y == 1 and x != '1':
		print(n + 1)
	elif y != 1:
		x = x[::-1]
		t = x.index('1')
		res = '0' * t + '1' + '0' * (len(x) - (t + 1))
		res = res[::-1]
		print(int(res, 2))
	num -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = bin(n)[2:]
	if n & 1:
		if n == 1:
			print(3)
		else:
			print(1)
	else:
		S = s.rstrip('0')
		if S == '1':
			print(n + 1)
		else:
			x = len(s)
			i = x - 1
			while s[i] != '1':
				i -= 1
			p = x - 1 - i
			print(2 ** p)


for i in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
		continue
	b_x = bin(x)[2:][::-1]
	l = len(b_x)
	for j in range(l):
		if b_x[j] == '1':
			if b_x == '0' * j + '1':
				print(2 ** j + 1)
			else:
				print(2 ** j)
			break


n = int(input())
datas = []
for i in range(n):
	l = int(input())
	datas.append(l)

def solve(n):
	if n == 1:
		return 3
	f = None
	r = False
	ss = str(bin(n))[2:][::-1]
	for (i, l) in enumerate(ss):
		if l == '0':
			continue
		if f is None:
			f = i
		elif r is False:
			r = True
	ret = 1
	ret = ret << f
	if not r:
		ret += 1
	return ret
for n in datas:
	print(solve(n))


for _ in range(int(input())):
	n = int(input())
	b = bin(n)[2:]
	while 1:
		break
	if n == 1 or n == 2:
		print(3)
		continue
	if b.count('0') == len(b) - 1:
		print(n + 1)
		while 1:
			break
	else:
		c = 0
		for i in range(len(b) - 1, -1, -1):
			if b[i] == '1':
				break
			else:
				c += 1
		print(2 ** c)


import math

def last_power(n):
	l = []
	while n > 1:
		t = math.ceil(2 ** int(math.log(n, 2)))
		n -= t
		l.append(t)
	return l
t = int(input())
for _ in range(t):
	x = int(input())
	if x % 2 != 0:
		if x == 1:
			print(3)
		else:
			print(1)
	else:
		l = last_power(x)
		if len(l) == 1:
			print(x + 1)
		else:
			print(l[-1])


def f(x):
	for i in range(len(x) - 1, -1, -1):
		if x[i] == '1':
			return len(x) - i - 1
	return -1
N = int(input())
for i in range(N):
	x = int(input())
	y = bin(x)[2:]
	m = f(y)
	ans = ''
	for i in range(int(m)):
		ans = ans + '0'
	ans = '1' + ans
	if len(y) == len(ans):
		ans = int(ans) + 1
	else:
		None
	ans = str(ans)
	if x == 1:
		print(3)
	else:
		print(int(ans, 2))


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		if not n & n - 1:
			print(n + 1)
		else:
			print(n & ~(n - 1))
	elif n > 1:
		print(1)
	else:
		print(3)


for i in range(int(input())):
	f = int(input())
	x = f
	f = str(bin(f))
	f = f[2:]
	f = f[::-1]
	if x == 1:
		print('3')
	elif 2 ** f.index('1') == x:
		print(x + 1)
	else:
		print(min(2 ** f.index('1'), x + 1))


for i in range(int(input())):
	x = int(input())
	pos1 = 0
	while True:
		if x & 1 == 1:
			break
		x = x >> 1
		pos1 += 1
	x = x >> 1
	if x > 0:
		print(1 << pos1)
	elif pos1 == 0:
		print(3)
	else:
		print((1 << pos1) + 1)


import math
for T in range(int(input())):
	a = int(input())
	if a % 2 == 0:
		x = a
		if x and (not x & x - 1) != 0:
			print(a + 1)
		else:
			n = a
			print(2 ** (int(math.log2(n & -n) + 1) - 1))
	elif a == 1:
		print(3)
	else:
		print(1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
	else:
		b = bin(n)[2:][::-1]
		s = ''
		for i in b:
			if i == '0':
				s += i
			elif i == '1':
				s = i + s
				break
		s = int(s, 2)
		if s ^ n > 0:
			print(s)
		else:
			print(s + 1)


def isPowerOfTwo(n):
	return n and (not n & n - 1)
for _ in range(int(input())):
	x = int(input())
	bn = bin(x)[2:]
	l = len(bn)
	lis = []
	if isPowerOfTwo(x):
		req_bn = '1' + '0' * (l - 2) + '1'
	else:
		for i in range(l - 1, -1, -1):
			if bn[i] == '0':
				lis.append('0')
			else:
				lis.append('1')
				break
		lis = lis[::-1]
		req_bn = ''.join(lis)
	print(int(req_bn, 2))


import sys
input = sys.stdin.readline

def rightmost_bit(x, d):
	c = 0
	while x > 0:
		if x % 2 == d:
			return c
		x = x // 2
		c += 1
	if d == 0:
		return c

def main():
	n_t = int(input())
	for _ in range(n_t):
		x = int(input())
		rm1 = rightmost_bit(x, 1)
		res = 1 << rm1
		if res == x:
			rm0 = rightmost_bit(x, 0)
			res += 1 << rm0
		print(res)
main()


n = int(input())
for i in range(n):
	x = int(input())
	y = str(bin(x)[2:])
	y = '0' + y
	n0 = y.rfind('0')
	n1 = y.rfind('1')
	if n1 > n0:
		if y == '01':
			y = '1' + y[n1:]
		else:
			y = y[n1:]
	elif y[:n1].rfind('1') > 0:
		y = y[n1:]
	else:
		y = y[n1:n0] + '1' + y[n0 + 1:]
	print(int(y, 2))


n = int(input())
for i in range(n):
	a = int(input())
	if a == 1:
		print(3)
	elif a % 2 == 1:
		print(1)
	else:
		a = str(bin(a))[2:]
		x = len(a)
		for j in range(x):
			if a[-1 - j] == '1':
				if j + 1 == len(a):
					a = '1' + str('0' * (x - 2)) + '1'
				else:
					a = '1' + '0' * j
				print(int(a, 2))
				break


for _ in range(int(input())):
	x = int(input())
	if x == 1:
		print(3)
	else:
		b = bin(x)[2:]
		c1 = b.count('1')
		if c1 == 1:
			if b[-1] == '1':
				print(3)
			elif b[0] == '1':
				print(2 ** (len(b) - 1) + 1)
			else:
				count = -1
				for i in range(len(b) - 1, -1, -1):
					count += 1
					if b[i] == '1':
						break
				print(2 ** count)
		elif b[-1] == '1':
			print(1)
		else:
			count = -1
			for i in range(len(b) - 1, -1, -1):
				count += 1
				if b[i] == '1':
					break
			print(2 ** count)


for ir in range(int(input())):
	n = int(input())
	if n == 1:
		print(3)
	elif n % 2 == 1:
		print(1)
	else:
		k = 2
		while n % k == 0:
			k = k + k
		if n == k // 2:
			print(n + 1)
		else:
			print(k // 2)