Petya and his friend, robot Petya++, like to solve exciting math problems.

One day Petya++ came up with the numbers $n$ and $x$ and wrote the following equality on the board: $$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$ where $\&$ denotes the bitwise AND operation . Then he suggested his friend Petya find such a minimal $m$ ($m \ge n$) that the equality on the board holds.

Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.

Can you solve this difficult problem?


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows.

The only line of each test case contains two integers $n$, $x$ ($0\le n, x \le 10^{18}$).


-----Output-----

For every test case, output the smallest possible value of $m$ such that equality holds.

If the equality does not hold for any $m$, print $-1$ instead.

We can show that if the required $m$ exists, it does not exceed $5 \cdot 10^{18}$.


-----Examples-----

Input
5
10 8
10 10
10 42
20 16
1000000000000000000 0
Output
12
10
-1
24
1152921504606846976


-----Note-----

In the first example, $10\ \&\ 11 = 10$, but $10\ \&\ 11\ \&\ 12 = 8$, so the answer is $12$.

In the second example, $10 = 10$, so the answer is $10$.

In the third example, we can see that the required $m$ does not exist, so we have to print $-1$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics


Solutions:
def read_test():
	nums = input().split(' ')
	return (int(nums[0]), int(nums[1]))

def read_input():
	test_num = int(input())
	tests = []
	for _ in range(test_num):
		tests.append(read_test())
	return tests

def solve(test):
	n = test[0]
	x = test[1]
	if n == x:
		return n
	n_binary = format(n, 'b')
	x_binary = format(x, 'b')
	if len(x_binary) < len(n_binary):
		x_binary = '0' * (len(n_binary) - len(x_binary)) + x_binary
	if len(n_binary) < len(x_binary):
		n_binary = '0' * (len(x_binary) - len(n_binary)) + n_binary
	diff_idx = 0
	while n_binary[diff_idx] == x_binary[diff_idx]:
		diff_idx += 1
	if x_binary[diff_idx] == '1':
		return -1
	if '1' in x_binary[diff_idx:]:
		return -1
	if diff_idx == 0:
		return int('1' + '0' * len(n_binary), 2)
	if n_binary[diff_idx - 1] != '0':
		return -1
	return int(n_binary[:diff_idx - 1] + '1' + '0' * (len(n_binary) - diff_idx), 2)

def main():
	tests = read_input()
	for test in tests:
		print(solve(test))
main()


t = int(input())
for _ in range(t):
	(n, goal) = map(int, input().split())
	bin_n = bin(n)
	length_n = len(bin_n) - 2
	bin_goal = bin(goal)
	length_goal = len(bin_goal) - 2
	if n == goal:
		print(n)
	elif goal == 0:
		print(2 ** length_n)
	elif n < goal or length_goal != length_n:
		print(-1)
	else:
		bin_goal = bin(goal)
		length_goal = len(bin_goal) - 2
		m = 0
		possible = True
		is_1 = [0, False]
		if bin_goal[-1] == '1':
			print(-1)
			continue
		for i in range(2, length_goal + 1):
			if bin_goal[-i] == '1':
				index = i
				break
		if bin_goal[:-index + 1] != bin_n[:-index + 1]:
			print(-1)
			continue
		m += goal
		for i in range(1, index):
			if bin_n[-i] == '1':
				is_1[1] = True
			elif is_1[1]:
				is_1 = [i - 1, False]
		if not possible or is_1[1]:
			print(-1)
		elif is_1[0]:
			print(m + 2 ** is_1[0])
		else:
			print(m)


t = int(input())
for tc in range(t):
	(n, x) = map(int, input().split())
	if n == x:
		print(x)
		continue
	sn = bin(n)[2:]
	ln = len(sn)
	sx = bin(x)[2:]
	lx = len(sx)
	if x == 0:
		print(1 << ln)
		continue
	if ln != lx:
		print(-1)
		continue
	i = 0
	while sn[i] == sx[i]:
		i += 1
	if '1' in sx[i + 1:]:
		print(-1)
		continue
	if sn[i] == '1':
		if i > 0 and sn[i - 1] == '1':
			print(-1)
		else:
			tmp = sn[:i - 1] + '1' + '0' * (ln - i)
			print(int(tmp, base=2))
	else:
		print(-1)


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	ab = bin(a)[2:]
	bb = bin(b)[2:]
	x = a
	y = a
	found = False
	while x > 0:
		if x == b:
			found = True
			print(y)
			break
		y += y & -y
		x &= y
	if b == 0:
		print(y)
	elif not found:
		print(-1)


def get_bigger_pow_2(n):
	p = 1
	i = 0
	while p <= n:
		p *= 2
		i += 1
	return (p, i)

def main():
	t = int(input())
	for _ in range(t):
		(n, x) = list(map(int, input().split(' ')))
		if n | x != n:
			print(-1)
			continue
		xor = n ^ x
		(p, i) = get_bigger_pow_2(xor)
		m = n >> i << i
		if (m & 1 << i + 1) >> i == 1:
			print(-1)
			continue
		if p != 1:
			m += p
		if m & n == x:
			print(m)
		else:
			print(-1)
main()


for i in range(int(input())):
	(n, x) = map(int, input().split())
	(a, b, p) = (n, n, False)
	while a > 0:
		if a == x:
			p = True
			print(b)
			break
		b += b & -b
		a &= b
	if x == 0:
		print(b)
	elif p == False:
		print(-1)


ta_rF = int(input())
for i in range(ta_rF):
	(fl_Gd, Y_q) = map(int, input().split())
	(H_mn_P, u_iRp, df_Bn) = (fl_Gd, fl_Gd, False)
	while H_mn_P > 0:
		if H_mn_P == Y_q:
			df_Bn = True
			print(u_iRp)
			break
		u_iRp += u_iRp & -u_iRp
		H_mn_P &= u_iRp
	if Y_q == 0:
		print(u_iRp)
	elif df_Bn == False:
		print(-1)


t = int(input(''))
for _ in range(t):
	(n, x) = [int(x) for x in input('').split(' ')]
	if x > n:
		print(-1)
		continue
	if x & n != x:
		print(-1)
		continue
	if x == n:
		print(n)
		continue
	s1 = bin(n)[2:]
	s2 = bin(x)[2:]
	s2 = '0' * (len(s1) - len(s2)) + s2
	l = len(s1)
	left10 = -1
	right11 = l + 1
	for i in range(l):
		if s1[i] == '1' and s2[i] == '0':
			left10 = l - 1 - i
			break
	for i in range(l - 1, -1, -1):
		if s1[i] == '1' and s2[i] == '1':
			right11 = l - 1 - i
			break
	if left10 == -1:
		print(n)
		continue
	if right11 <= left10 + 1:
		print(-1)
		continue
	z = 1 << left10 + 1
	print((n & -z) + z)


def solve(n, x):
	if n < x:
		print(-1)
		return
	if n == x:
		print(n)
		return
	bn = bin(n)[2:][::-1]
	bx = bin(x)[2:][::-1]
	bm = bn[:]
	if x == 0:
		print(2 ** len(bn))
		return
	if len(bx) != len(bn):
		print(-1)
		return
	last1 = -1
	no_more = False
	for i in range(len(bn)):
		if bn[i] == '0' and bx[i] == '1':
			print(-1)
			return
		if bn[i] == '1':
			if bx[i] == '1':
				no_more = True
			else:
				if no_more:
					print(-1)
					return
				last1 = i
				bm = bm[:i] + '0' + bm[i + 1:]
	if bx[last1 + 1] == '1':
		print(-1)
		return
	bm = bm[:last1 + 1] + '1' + bm[last1 + 2:]
	print(int(bm[::-1], 2))
t = int(input())
for i in range(t):
	s = input()
	(n, x) = (int(s.split()[0]), int(s.split()[1]))
	solve(n, x)


t = int(input())

def solve():
	s = input()
	n = int(s.split(' ')[0])
	x = int(s.split(' ')[1])
	if n == x:
		print(n)
		return
	for i in range(70, -1, -1):
		if n >> i & 1 != x >> i & 1:
			if n >> i & 1 == 0:
				print(-1)
				return
			else:
				if n >> i + 1 & 1 == 0 and x & (1 << i + 1) - 1 == 0:
					ans = (n >> i + 2 << i + 2) + (1 << i + 1)
					if ans > 5000000000000000000:
						print(ans)
						return
					print(ans)
					return
				print(-1)
				return
while t:
	t -= 1
	solve()


for j in range(int(input())):
	(b, c) = [int(j) for j in input().split()]
	bc = bin(b)[2:]
	cc = bin(c)[2:]
	y = b
	z = b
	found = False
	while y > 0:
		if y == c:
			found = True
			print(z)
			break
		z += z & -z
		y &= z
	if c == 0:
		print(z)
	elif not found:
		print(-1)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = n
	b = n
	f = 1
	while a > 0:
		if a == x:
			f = 0
			print(b)
			break
		b += b & -b
		a &= b
	if x == 0:
		print(b)
	elif f:
		print(-1)


t = int(input())
for i in range(t):
	arr = list(map(int, input().split()))
	n = arr[0]
	x = arr[1]
	t1 = n
	temp = n
	fnd = 0
	while t1 > 0:
		if t1 == x:
			fnd = 1
			break
		temp = temp + (temp & -temp)
		t1 = t1 & temp
	if fnd != 0 or x == 0:
		print(temp)
	elif fnd == 0:
		print('-1')


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	max_bit = 63
	(n, x) = ii()
	xor = n ^ x
	left = 0
	if xor == 0:
		print(n)
		continue
	while left < 63 and xor >> max_bit - left & 1 == 0:
		left += 1
	bit = max_bit - left
	m = (n >> bit) + 1 << bit
	if m & n != x:
		print(-1)
	else:
		print(m)


def mapped_read(cast):
	return map(cast, input().split())

def read_list(cast):
	return list(mapped_read(cast))

def count(a):
	ans = 0
	while a > 0:
		a //= 2
		ans += 1
	return ans

def f(x):
	cnt = 0
	while x % 4 == 0:
		x //= 2
		cnt += 1
	return cnt

def solve():
	(n, x) = mapped_read(int)
	if n == x:
		print(n)
		return
	if x == 0:
		print(2 ** count(n))
		return
	cnt = f(x)
	if (2 ** count(n) - 1 ^ 2 ** cnt - 1) & n != x:
		print(-1)
		return
	print(n + 2 ** count(n & 2 ** cnt - 1) - (n & 2 ** cnt - 1))
(n,) = mapped_read(int)
for _ in range(n):
	solve()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	(nn, xx) = (n, x)
	flag = 0
	if n < x:
		print(-1)
	elif n == x:
		print(n)
	else:
		cnt = 0
		(a, b) = (str(bin(n))[2:], str(bin(x))[2:])
		b = '0' * (len(a) - len(b)) + b
		cnt = len(a)
		flag = 0
		ans = ''
		for i in range(len(a)):
			if a[i] == b[i] and flag == 0:
				ans += a[i]
			else:
				flag = 1
				ans += '1'
		ans = int(ans, 2) + 1
		if xx <= ans & ans - 1:
			print(ans)
		else:
			print(-1)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	if len(bin(x)) > len(bin(n)):
		print(-1)
		continue
	bin_n = bin(n)
	bin_x = bin(x)
	if len(bin_x) < len(bin_n):
		if x:
			print(-1)
			continue
		bin_x = '0b' + '0' * (len(bin_n) - len(bin_x)) + bin_x[2:]
	i = len(bin_x) - 1
	while i >= 2 and bin_x[i] == '0':
		i -= 1
	p = len(bin_x) - i - 1
	i = 2
	while i < len(bin_n):
		if bin_n[i] == '1' and bin_x[i] == '0':
			if p >= len(bin_n) - i:
				if i == 2 or bin_x[i - 1] != '1':
					s = bin_n[i:]
					print(n + 2 ** len(s) - int(s, 2))
				else:
					print(-1)
			else:
				print(-1)
			break
		elif bin_n[i] == '0' and bin_x[i] == '1':
			print(-1)
			break
		i += 1
	else:
		print(n)


t = int(input())
for _ in range(t):
	(n, x) = [int(i) for i in input().split()]
	if n == x:
		print(n)
		continue
	if x > n:
		print(-1)
	else:
		x_b = bin(x)[2:]
		n_b = bin(n)[2:]
		le = max(len(x_b), len(n_b))
		x_b = '0' * (le - len(x_b)) + x_b
		n_b = '0' * (le - len(n_b)) + n_b
		chislo = ''
		add = ''
		f = 0
		for i in range(le):
			if f and x_b[i] == '1':
				print(-1)
				break
			elif f:
				chislo = chislo + '0'
			elif x_b[i] == n_b[i] == '1':
				chislo = chislo + '1'
			elif x_b[i] == '0' and n_b[i] == '1':
				if chislo and chislo[-1] == '1':
					print(-1)
					break
				chislo = chislo[:-1] + '10'
				f = 1
			elif x_b[i] == '1' and n_b[i] == '0':
				print(-1)
				break
			else:
				chislo = chislo + '0'
		else:
			print(int(chislo, 2))


def solve():
	(n, x) = map(int, input().split())
	if x > n:
		print(-1)
		return
	n = bin(n)[2:]
	x = bin(x)[2:]
	ln = len(n)
	lx = len(x)
	ans = []
	if x == '0':
		if n == '0':
			print(0)
			return
		myans = '1' + '0' * ln
		print(int(myans, 2))
		return
	if lx < ln:
		print(-1)
		return
	for i in range(lx):
		ans.append(x[i])
		if n[i] == '0' and x[i] == '1':
			print(-1)
			return
	la = len(ans)
	for i in range(la):
		if n[i] < ans[i]:
			myans = ''.join(ans)
			print(int(myans, 2))
			return
		elif n[i] > ans[i]:
			for j in range(i - 1, -1, -1):
				if ans[j] == '0':
					ans[j] = '1'
					for k in range(j + 1, la):
						if x[k] != '0':
							print(-1)
							return
					myans = ''.join(ans)
					print(int(myans, 2))
					return
			print(-1)
			return
	myans = ''.join(ans)
	print(int(myans, 2))
	return
for _ in range(int(input())):
	solve()


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n & k != k:
		print(-1)
		continue
	if n == k:
		print(n)
		continue
	if k > n:
		print(-1)
		continue
	if k == 0:
		lenn = int(math.log2(n))
		print(1 << lenn + 1)
		continue
	lenk = int(math.log2(k)) + 1
	b = lenk
	for i in range(lenk - 1, -1, -1):
		if k >> i & 1 == 1:
			b = i
	lenn = int(math.log2(n)) + 1
	if lenn != lenk:
		print(-1)
		continue
	flag = False
	for i in range(b, lenk + 1):
		if n >> i & 1 != k >> i & 1:
			flag = True
			break
	if flag:
		print(-1)
		continue
	if n >> b - 1 & 1 == 1:
		print(-1)
		continue
	for i in range(b - 1, -1, -1):
		if n >> i & 1 == 1:
			c = i
			break
	m = n >> b
	m = m << b
	m += 1 << c + 1
	print(m)


for _ in range(int(input())):
	[n, x] = list(map(int, input().split()))
	(orin, orix) = (n, x)
	if n == x:
		print(n)
		continue
	if n < x:
		print(-1)
		continue
	maxi = 0
	power = 0
	yes = 1
	while n or x:
		if x % 2 == 1 and n % 2 == 0:
			print(-1)
			yes = 0
			break
		if x % 2 == 1 and n % 2 == 1:
			if n != x:
				print(-1)
				yes = 0
				break
			elif power == maxi + 1:
				print(-1)
				yes = 0
				break
			else:
				print(orix + 2 ** (maxi + 1))
				yes = 0
				break
		if x % 2 == 0 and n % 2 == 1:
			maxi = power
		(n, x) = (n // 2, x // 2)
		power += 1
	if yes == 1:
		print(2 ** (maxi + 1))


def bin_to_dec(x):
	y = 0
	for i in x:
		y *= 2
		y += int(i)
	return y
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = bin(n)
	b = bin(x)
	if n == x:
		print(n)
		continue
	if x == 0:
		print(1 << len(a) - 2)
		continue
	if n < x:
		print(-1)
		continue
	a = a[2:]
	b = b[2:]
	if len(a) != len(b):
		print(-1)
		continue
	i = 0
	while i < len(a):
		if a[i] != b[i]:
			break
		i += 1
	k = i
	ans = 1
	while k < len(b):
		if b[k] != '0':
			ans = 0
		k += 1
	if not ans:
		print(-1)
		continue
	if a[i - 1] == '1':
		print(-1)
		continue
	else:
		l = []
		j = 0
		while j < i - 1:
			l.append(a[j])
			j += 1
		l.append('1')
		for w in range(len(a) - i):
			l.append('0')
		s = ''
		for char in l:
			s = s + char
		print(bin_to_dec(s))


for j in range(int(input())):
	(n, x) = map(int, input().split())
	if n == x:
		print(n)
		continue
	if x > n:
		print('-1')
		continue
	a = list(bin(n)[2:])
	b = list(bin(x)[2:])
	t = len(b)
	s = len(a) - t
	b1 = ['0'] * s
	b = b1 + b
	f = 0
	r = len(a)
	j = r - 1
	t = 0
	while True:
		if j == -1:
			break
		if b[j] == '1' and a[j] == '0':
			t = 1
			print('-1')
			break
		if b[j] == '1' and a[j] == '1':
			f = 1
		if a[j] == '1' and b[j] == '0' and (f == 1):
			print('-1')
			t = 1
			break
		j -= 1
	if t == 1:
		continue
	flg = 0
	req = 0
	for j in range(r):
		if a[j] == '1' and b[j] == '0':
			req = j
			break
	if req != 0:
		reqs = ''.join(a[0:req - 1])
	else:
		reqs = ''
	reqs = reqs + '1'
	rem = ''.join(['0'] * (r - req))
	reqs = reqs + rem
	if int(reqs, 2) < n:
		print(-1)
		continue
	print(int(reqs, 2))


def func():
	(a, b) = map(int, input().split())
	if b > a:
		print(-1)
		return
	if b == a:
		print(a)
		return
	c = a - b
	d = a
	ld = []
	lc = []
	cnt = 0
	while d != 0:
		if d % 2 != 0:
			ld.append(cnt)
		d = d // 2
		cnt = cnt + 1
	cnt = 0
	while c != 0:
		if c % 2 != 0:
			lc.append(cnt)
		c = c // 2
		cnt = cnt + 1
	if cnt in ld:
		print(-1)
		return
	ans = a + pow(2, cnt)
	for i in range(len(lc)):
		if lc[i] not in ld or lc[i] != ld[i]:
			print(-1)
			return
		ans = ans - pow(2, lc[i])
	print(ans)
for i in range(int(input())):
	func()


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	max_bit = 63
	(n, x) = ii()
	if n == x:
		print(n)
		continue
	if n < x:
		print(-1)
		continue
	arr_n = [0] * max_bit
	arr_x = [0] * max_bit
	for i in range(max_bit):
		arr_n[max_bit - i - 1] = n >> i & 1
		arr_x[max_bit - i - 1] = x >> i & 1
	left = 0
	flag = True
	while left < max_bit:
		if arr_n[left] == arr_x[left]:
			left += 1
		elif arr_n[left] > arr_x[left]:
			break
		else:
			flag = False
			break
	if flag:
		bit = max_bit - left
		m = (n >> bit) + 1 << bit
		if m & n != x:
			flag = False
		else:
			print(m)
	if not flag:
		print(-1)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	(st, st1) = (bin(n)[2:], bin(x)[2:])
	if n & x != x:
		print(-1)
	elif n == x:
		print(x)
	else:
		while len(st) != 64:
			st = '0' + st
		while len(st1) != 64:
			st1 = '0' + st1
		vsp = [0] * 64
		vsp[63] = int(st1[63])
		for i in range(62, -1, -1):
			vsp[i] = vsp[i + 1] + int(st1[i])
		ind = -1
		i = 0
		while st[i] == st1[i]:
			if vsp[i] == 0:
				ind = i
			i += 1
		if ind == -1:
			print(-1)
		else:
			res = st1[:ind] + '1' + '0' * (64 - ind - 1)
			print(int(res, 2))


for _ in range(int(input())):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	if b > a:
		print(-1)
		continue
	if b == a:
		print(a)
		continue
	n = str(bin(a))[2:]
	c = str(bin(b))[2:]
	if b == 0:
		print(2 ** len(n))
		continue
	if len(c) != len(n):
		print(-1)
		continue
	possible = True
	spot = 0
	thing2 = False
	ans = 0
	for r in range(len(n)):
		if thing2 and c[r] == '1':
			possible = False
			break
		if n[r] != c[r]:
			if c[r] != '0' or c[r - 1] != '0':
				possible = False
				break
			elif not thing2:
				thing2 = True
				spot = len(n) - r
				ans += 2 ** spot
		if not thing2:
			ans += 2 ** (len(n) - r - 1) * int(n[r])
	if not possible:
		print(-1)
	else:
		print(ans)


def find_m(n, x):
	f = [0] * 60
	for i in range(60):
		if ~n >> i & 1:
			f[i] = n
		else:
			f[i] = (n & ~((1 << i) - 1)) + (1 << i)
	m = n
	for i in range(60):
		if ~x >> i & 1:
			m = max(m, f[i])
	for i in range(60):
		if x >> i & 1:
			if m >= f[i]:
				return -1
	return m

def main():
	t = int(input())
	for i in range(t):
		(n, x) = map(int, input().split())
		result = find_m(n, x)
		print(result)
main()


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split(' '))
	if n < x:
		print(-1)
		continue
	m = n
	current_bit = 0
	current_num = n
	while current_num != x and m < 1e+19:
		m += 1 << current_bit
		if (m >> current_bit) % 2 == 0:
			current_bit += 1
		current_num &= m
	if m >= 1e+19:
		print(-1)
	else:
		print(m)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	N = [0] * 62
	X = [0] * 62
	f = True
	for i in range(62):
		if n & 1 << i:
			N[i] += 1
		if x & 1 << i:
			X[i] += 1
		if X[i] and (not N[i]):
			f = False
			break
	if not f:
		print(-1)
		continue
	i = 0
	a = 0
	p = 0
	while i < 62:
		if N[i] and (not X[i]):
			a += 2 ** i
			N[i] = 0
			if p != 0:
				a -= 2 ** p
				p = 0
			j = i + 1
			while j < 62:
				if N[j] and (not X[j]):
					N[j] = 0
					j += 1
				elif N[j] and X[j]:
					f = False
					break
				else:
					break
			i = j
			p = j
		elif N[i] == X[i] == 1:
			break
		else:
			i += 1
	if not f:
		print(-1)
		continue
	for i in range(62):
		if N[i] != X[i]:
			f = False
			break
	if not f:
		print(-1)
		continue
	print(a + n)


T = int(input())

def b(a, b):
	return a >> b & 1
for t in range(T):
	(n, x) = map(int, input().split())
	(low, high) = (n, 10 ** 20)
	ac = 0
	for i in range(max(x.bit_length(), n.bit_length())):
		if not b(n, i) and (not b(x, i)):
			pass
		elif not b(n, i) and b(x, i):
			low = -1
			break
		elif b(n, i) and (not b(x, i)):
			low = n + ac + 1
		else:
			high = n + ac
		if not b(n, i):
			ac += 2 ** i
		if low > high:
			low = -1
			break
	print(low)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	f = 0
	for i in range(64):
		if n >> i & 1 and x >> i & 1:
			f = 1
		if f == 1 and n >> i & 1 and (x >> i & 1 == 0):
			f = 2
			break
		if n >> i & 1 == 0 and x >> i & 1:
			f = 2
			break
	if f == 2:
		print(-1)
		continue
	ans = 0
	for i in range(64, -1, -1):
		if n >> i & 1 and x >> i & 1 == 0:
			ans = 1 << i + 1
			r = 0
			for j in range(i + 1):
				if n >> j & 1:
					r += 1 << j
			ans -= r
			break
	n += ans
	f = 0
	for i in range(64):
		if n >> i & 1 == 0 and x >> i & 1:
			f = 1
			break
	if f:
		print(-1)
	else:
		print(n)


for _ in range(int(input())):
	(m, x) = map(int, input().split())
	dicM = {}
	dicX = {}
	ok = True
	pos = -1
	A = -1
	ans = 0
	for i in range(63):
		if 1 << i & x != 0:
			dicX[i] = 1
		else:
			dicX[i] = 0
		if 1 << i & m != 0:
			dicM[i] = 1
		else:
			dicM[i] = 0
		if dicM[i] != dicX[i]:
			if dicM[i] == 1:
				pos = i + 1
			else:
				ok = False
		elif dicX[i] == 1 and dicX[i] == dicM[i]:
			ans += 1 << i
			A = i
		if A != -1 and pos != -1 and (pos >= A):
			ok = False
	if pos != -1:
		ans += 1 << pos
	print(ans) if ok else print('-1')


import sys
input = sys.stdin.readline
MAX = int(1e+18)

def solve():
	(N, X) = list(map(int, input().split()))
	if N == X:
		print(N)
	elif X == 0:
		A = 1
		while A <= N:
			A <<= 1
		print(A)
	else:
		A = list(bin(N)[2:])
		N1 = len(A)
		D = {}
		for i in range(N1 - 1, 0, -1):
			if A[i - 1] + A[i] == '01':
				A[i] = '0'
				A[i - 1] = '1'
				t = eval('0b' + ''.join(A))
				A[i - 1] = '0'
				x = eval('0b' + ''.join(A))
				D[x] = min(D.get(x, MAX), t)
			elif A[i] == '1':
				A[i] = '0'
		if X in D:
			print(D[X])
		else:
			print(-1)
for _ in range(int(input())):
	solve()


def solve():
	(n, x) = map(int, input().split())
	if n == x:
		print(n)
		return
	for bitOff in range(70):
		bit = 1 << bitOff
		if not n & bit:
			continue
		tmpN = n
		for smallOff in range(bitOff - 1, -1, -1):
			smallBit = 1 << smallOff
			if tmpN & smallBit:
				tmpN ^= smallBit
		tmpN += bit
		result = n & tmpN
		for smallOff in range(bitOff, -1, -1):
			smallBit = 1 << smallOff
			if result & smallBit:
				result ^= smallBit
		if result == x:
			print(tmpN)
			return
	print(-1)

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