JJ has three integers N, A and B where 0 ≤ A, B < 2^{N}. He wants to find a third integer X such that:
0 ≤ X < 2^{N}
the value of (A \oplus X) \times (B \oplus X) is maximum.

Here \oplus represents the [Bitwise XOR] operator.

Can you help him find such an integer X? If there are multiple integers which satisfy the given conditions, print any.  

------ Input Format ------ 

- The first line will contain T - number of test cases. Then the test cases follow.
- The first and only line of each test case contains three integers N, A and B - the integers mentioned in the problem statement. 

------ Output Format ------ 

For each test case, output an integer X which satisfies the given conditions. 

If multiple answers exist, print any.

------ Constraints ------ 

$1 ≤ T ≤ 5000$
$1 ≤N ≤30$
$0 ≤A, B < 2^{N}$

----- Sample Input 1 ------ 
3
1 0 0
3 4 6
2 2 1

----- Sample Output 1 ------ 
1
3
0

----- explanation 1 ------ 
Test case 1: For $X = 1$, $(0 \oplus 1) \times (0 \oplus 1) = 1$ which can be proven to be the maximum value of this expression.

Test case 2: For $X = 3$, $(4 \oplus 3) \times (6 \oplus 3) = 35$ which can be proven to be the maximum value of this expression.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
for _ in range(int(input())):
	(N, A, B) = map(int, input().split())
	(A_Temp, B_Temp) = (A, B)
	C = 0
	D = 0
	E = 0
	for i in range(N):
		currentBit = 2 ** (N - i - 1)
		count = 0
		if A_Temp >= currentBit:
			A_Temp -= currentBit
			count += 1
		if B_Temp >= currentBit:
			B_Temp -= currentBit
			count += 1
		if count == 1 and D == 0:
			D += currentBit
		elif count == 1:
			E += currentBit
		elif count == 2 or count == 0:
			C += currentBit
	Sum = 2 ** N - C - 1
	D = Sum - E
	X = C + D ^ A
	print(X)


t = int(input())
while t > 0:
	(n, a, b) = map(int, input().split())
	xor = 0
	flag = False
	for i in range(n - 1, -1, -1):
		if a & 1 << i and b & 1 << i:
			continue
		elif a & 1 << i == 0 and b & 1 << i == 0:
			xor = xor | 1 << i
		elif flag == False:
			if a & 1 << i == 0:
				xor = xor | 1 << i
			flag = True
		elif b & 1 << i == 0:
			xor = xor | 1 << i
	print(xor)
	t -= 1


def solve():
	for t in range(int(input())):
		(N, A, B) = list(map(int, input().split()))
		x = 0
		flag = False
		for i in range(N - 1, -1, -1):
			if A & 1 << i == B & 1 << i:
				if A & 1 << i == 0:
					x += 1 << i
			elif flag == False:
				flag = True
				if A & 1 << i == 0:
					x += 1 << i
			elif B & 1 << i == 0:
				x += 1 << i
		print(x)
solve()


def solve():
	for T in range(int(input())):
		(n, a, b) = list(map(int, input().split()))
		X = 0
		flag = False
		for i in range(n - 1, -1, -1):
			if a & 1 << i == b & 1 << i:
				if a & 1 << i == 0:
					X += 1 << i
			elif flag == False:
				flag = True
				if a & 1 << i == 0:
					X += 1 << i
			elif b & 1 << i == 0:
				X += 1 << i
		print(X)
solve()


def sol():
	(n, a, b) = map(int, input().split())
	xor = 0
	flag = False
	for i in range(n - 1, -1, -1):
		if a & 1 << i and b & 1 << i:
			continue
		elif a & 1 << i == 0 and b & 1 << i == 0:
			xor = xor | 1 << i
		elif flag == False:
			if a & 1 << i == 0:
				xor = xor | 1 << i
			flag = True
		elif b & 1 << i == 0:
			xor = xor | 1 << i
	print(xor)
for _ in range(int(input())):
	sol()


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	big_bin_a = '{:032b}'.format(a)
	big_bin_b = '{:032b}'.format(b)
	bin_a = big_bin_a[32 - n:]
	bin_b = big_bin_b[32 - n:]
	k = n - 1
	x = 0
	done = False
	for i in range(0, n):
		if bin_a[i] == '0' and bin_b[i] == '0':
			x += 2 ** k
		if bin_a[i] == '0' and bin_b[i] == '1':
			if not done:
				x += 2 ** k
				done = True
		if bin_a[i] == '1' and bin_b[i] == '0':
			if done:
				x += 2 ** k
			else:
				done = True
		k -= 1
	print(x)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	mask = 0
	for i in range(n - 1, -1, -1):
		temp1 = mask
		temp2 = mask | 1 << i
		val1 = (a ^ temp1) * (temp1 ^ b)
		val2 = (a ^ temp2) * (temp2 ^ b)
		if val1 > val2:
			mask = temp1
		else:
			mask = temp2
	print(mask)


t = int(input())
for _ in range(t):
	(n, a, b) = [int(i) for i in input().split()]
	flag = 0
	res = 1
	x = 0
	for i in range(n - 1, -1, -1):
		res = 2 ** i
		if not res & a and (not res & b):
			x += 2 ** i
		elif res & a and res & b:
			pass
		elif not flag:
			if not res & a:
				x += 2 ** i
			else:
				pass
			flag += 1
		elif not res & b:
			x += 2 ** i
		else:
			pass
	print(x)


def solve():
	(n, a, b) = map(int, input().split())
	x = 0
	flag = True
	for i in range(n - 1, -1, -1):
		a1 = 1 << i & a
		b1 = 1 << i & b
		d = 1 << i
		if a1 == b1:
			if a1 == 0:
				x += d
		elif a1 != 0 and b1 == 0:
			if flag == True:
				flag = False
			else:
				x += d
		elif a1 == 0 and b1 != 0:
			if flag == True:
				flag = False
				x += d
	return x
for i in range(int(input())):
	print(solve())


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	ans = 0
	flag = True
	for i in range(n - 1, -1, -1):
		(x, y) = (1 << i & a, 1 << i & b)
		if x == 0 and y == 0:
			ans += 1 << i
		elif x != 0 and y == 0:
			if flag:
				flag = False
			else:
				ans += 1 << i
		elif x == 0 and y != 0:
			if flag:
				ans += 1 << i
				flag = False
	print(ans)


t = int(input())
while t:
	(n, a, b) = map(int, input().strip().split())
	s1 = bin(a)[2:]
	s2 = bin(b)[2:]
	diff = abs(len(s2) - len(s1))
	if len(s2) > len(s1):
		s1 = '0' * diff + s1
	if len(s1) > len(s2):
		s2 = '0' * diff + s2
	f = 0
	ans = ''
	for i in range(len(s2)):
		if s1[i] == s2[i]:
			if s1[i] == '1':
				ans += '0'
			else:
				ans += '1'
		elif f == 0:
			if s1[i] == '0':
				ans += '1'
				f = 1
			else:
				ans += '0'
				f = 1
		elif s2[i] == '0':
			ans += '1'
		else:
			ans += '0'
	if len(ans) < n:
		ans = '1' * (n - len(ans)) + ans
	print(int(ans, 2))
	t -= 1


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	limit = '1' + '0' * (a[0] - 1)
	bin_first = bin(a[1])[2:]
	bin_second = bin(a[2])[2:]
	if len(limit) > len(bin_first):
		bin_first = '0' * (len(limit) - len(bin_first)) + bin_first
	if len(bin_first) > len(bin_second):
		bin_second = '0' * (len(bin_first) - len(bin_second)) + bin_second
	elif len(bin_first) < len(bin_second):
		bin_first = '0' * (len(bin_second) - len(bin_first)) + bin_first
	ans = ''
	for j in range(len(bin_first)):
		if bin_first[j] == bin_second[j]:
			ans += '1'
		else:
			ans += '_'
	xor_key = ''
	statement = True
	for j in range(len(ans)):
		if ans[j] == '_':
			if statement:
				xor_key += '1'
				statement = False
			else:
				xor_key += '0'
		else:
			xor_key += ans[j]
	result = int(xor_key, 2) ^ int(bin_first, 2)
	print(result)


def conv_dec(lst):
	n = len(lst)
	ans = 0
	for i in range(n):
		if lst[i] == 1:
			ans += pow(2, i)
	return ans
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	ca = [0] * n
	cb = [0] * n
	i = 0
	j = 1
	while i < n:
		if a & j > 0:
			ca[i] = 1
		else:
			ca[i] = 0
		if b & j > 0:
			cb[i] = 1
		else:
			cb[i] = 0
		i += 1
		j = j * 2
	x = [0] * n
	flag = True
	for i in range(n - 1, -1, -1):
		if ca[i] == 0 and cb[i] == 0:
			x[i] = 1
		elif ca[i] == 1 and cb[i] == 0:
			if flag:
				flag = False
			else:
				x[i] = 1
		elif ca[i] == 0 and cb[i] == 1:
			if flag:
				flag = False
				x[i] = 1
	ans = conv_dec(x)
	print(ans)


import sys
f = sys.stdin
next(f)
for s in f:
	(n, a, b) = map(int, s.split())
	b ^= a
	r = ~(a | b) & (1 << n) - 1 | a & b
	if b:
		r ^= 1 << b.bit_length() - 1
	print(r)


import sys
f = sys.stdin
next(f)
for s in f:
	(n, a, b) = map(int, s.split())
	b ^= a
	c = b.bit_length()
	print(~(a | b) & (1 << n) - 1 | a & b ^ (c and 1 << c - 1))


def getithbit(num, i):
	mask = 1 << i
	if num & mask > 0:
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	l = [0] * n
	boo = True
	for k in range(n - 1, -1, -1):
		x = getithbit(a, k)
		y = getithbit(b, k)
		if x == 1 and y == 1:
			l[k] = 0
		elif x == 0 and y == 0:
			l[k] = 1
		elif boo == True:
			l[k] = y
			boo = False
		else:
			l[k] = x
	sumy = 0
	for q in range(0, n):
		if l[q] == 1:
			sumy += 2 ** q
	print(sumy)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	m = 0
	for i in range(n - 1, -1, -1):
		t1 = m
		t2 = m | 1 << i
		(p1, p2) = ((a ^ t1) * (b ^ t1), (a ^ t2) * (b ^ t2))
		if p1 > p2:
			m = t1
		else:
			m = t2
	print(m)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	mask = 0
	for i in range(n - 1, -1, -1):
		bit1 = a >> i & 1
		bit2 = b >> i & 1
		if bit1 == 0 and bit2 == 0:
			mask = mask | 1 << i
		elif bit1 == 1 and bit2 == 1:
			continue
		else:
			temp1 = mask
			temp2 = mask | 1 << i
			val1 = (a ^ temp1) * (temp1 ^ b)
			val2 = (a ^ temp2) * (temp2 ^ b)
			if val1 > val2:
				mask = temp1
			else:
				mask = temp2
	print(mask)


t = int(input())
for j in range(t):
	(n, a, b) = map(int, input().split())
	temp = 0
	boo = False
	for i in range(n - 1, -1, -1):
		if a >> i & 1 and b >> i & 1:
			continue
		elif a >> i & 1 or b >> i & 1:
			if not boo:
				boo = True
				if b >> i & 1:
					temp = temp | 1 << i
			elif a >> i & 1:
				temp = temp | 1 << i
		elif not a >> i & 1 and (not b >> i & 1):
			temp = temp | 1 << i
	print(temp)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	a = '0' * (n - len(bin(a)[2:])) + bin(a)[2:]
	b = '0' * (n - len(bin(b)[2:])) + bin(b)[2:]
	ans = ''
	carry = 0
	for i in range(n):
		if a[i] == b[i] and a[i] == '0':
			ans += '1'
		elif a[i] == b[i] and a[i] == '1':
			ans += '0'
		else:
			if carry == 0:
				if a[i] == '1':
					ans += '0'
				elif a[i] == '0':
					ans += '1'
			elif b[i] == '1':
				ans += '0'
			elif b[i] == '0':
				ans += '1'
			carry = 1
	print(int(ans, 2))


for s in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	m = 0
	c = 0
	for i in range(n):
		if a & 1 << i != b & 1 << i:
			m = max(m, 1 << i)
		else:
			c += 1 << i
	print(m + c ^ a)


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	l = [0] * n
	x = 0
	t = 0
	for i in range(n - 1, -1, -1):
		if a & 1 << i > 0:
			l[i] += 1
		if b & 1 << i > 0:
			l[i] += 1
		if l[i] == 0:
			x += 1 << i
		if l[i] == 1:
			if t == 0:
				t = 1
				if a & 1 << i == 0:
					x += 1 << i
			elif b & 1 << i == 0:
				x += 1 << i
	print(x)


t = int(input())
for i in range(t):
	(n, a, b) = list(map(int, input().split()))
	arr1 = [0] * 31
	arr2 = [0] * 31
	i = 0
	j = 1
	while i < n:
		if a & j > 0:
			arr1[i] = 1
		else:
			arr1[i] = 0
		if b & j > 0:
			arr2[i] = 1
		else:
			arr2[i] = 0
		i += 1
		j *= 2
	ans = 0
	f = 0
	for i in range(n - 1, -1, -1):
		if arr1[i] == 0 and arr2[i] == 0:
			ans = ans + (1 << i)
		elif arr1[i] == 1 and arr2[i] == 0:
			if f == 0:
				f += 1
			else:
				ans += 1 << i
		elif arr1[i] == 0 and arr2[i] == 1:
			if f == 0:
				f += 1
				ans += 1 << i
	print(ans)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	(count, res) = (0, 0)
	for i in range(n - 1, -1, -1):
		abit = 1 << i & a
		bbit = 1 << i & b
		if abit == bbit:
			if abit == 0:
				res |= 1 << i
		elif count == 0:
			if bbit:
				res |= 1 << i
			count += 1
		elif abit:
			res |= 1 << i
	print(res)


t = int(input())
for _ in range(t):
	(n, a, b) = [int(x) for x in input().split()]
	ans = 0
	flag = False
	for i in range(n - 1, -1, -1):
		ba = a >> i & 1
		bb = b >> i & 1
		an = 1 << i
		if ba == 0 and bb == 0:
			ans += an
		elif ba != bb:
			if not flag:
				if ba == 0:
					ans += an
				flag = True
			elif bb == 0:
				ans += an
	print(ans)


t = int(input())
for i in range(t):
	[N, A, B] = [int(i) for i in input().split()]
	arr1 = str(bin(A)[2:])
	arr2 = str(bin(B)[2:])
	A1 = len(arr1)
	B1 = len(arr2)
	arr2 = '0' * (N - B1) + arr2
	arr1 = '0' * (N - A1) + arr1
	ans = ''
	c = 0
	for i in range(N):
		if arr1[i] == arr2[i] and arr1[i] == '0':
			ans = ans + '1'
		elif arr1[i] == arr2[i] and arr1[i] == '1':
			ans = ans + '0'
		else:
			if c == 0:
				if arr1[i] == '1':
					ans = ans + '0'
				elif arr1[i] == '0':
					ans = ans + '1'
			elif arr2[i] == '1':
				ans = ans + '0'
			elif arr2[i] == '0':
				ans = ans + '1'
			c = 1
	print(int(ans, 2))


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	mx = c = 0
	for i in range(n):
		if a & 1 << i != b & 1 << i:
			mx = max(mx, 1 << i)
		else:
			c += 1 << i
	print(c + mx ^ a)


count = int(input())
for i in range(count):
	(count_inside, int_a, int_b) = list(map(int, input().split()))
	temp_A = 0
	maximum_val = 0
	for i in range(count_inside):
		temp_p = 1 << i
		sum_a = False
		sum_b = False
		if temp_p & int_a != 0:
			sum_a = True
		if temp_p & int_b != 0:
			sum_b = True
		if sum_a != sum_b:
			maximum_val = max(maximum_val, temp_p)
		else:
			temp_A += temp_p
	temp_A += maximum_val
	print(temp_A ^ int_a)


def solve(A):
	(n, b, a) = A
	x = 0
	p = -1
	for i in range(n - 1, -1, -1):
		if 1 << i & a > 0 and 1 << i & b > 0:
			continue
		elif 1 << i & a == 0 and 1 << i & b == 0:
			x |= 1 << i
		elif p == -1:
			if 1 << i & a == 0 and 1 << i & b > 0:
				p = 0
			else:
				p = 0
				x |= 1 << i
		elif 1 << i & a == 0 and 1 << i & b > 0:
			x |= 1 << i
	print(x)
t = int(input())
ans = []
for i in range(t):
	A = list(map(int, input().split()))
	ans.append(solve(A))