Given an integer N, Chef wants to find the smallest positive integer M such that the bitwise XOR of M and M+1 is N. If no such M exists output -1.

-----Input-----
The first line of input contain an integer T denoting the number of test cases. Each of the following T lines contains an integer N for that test case.

-----Output-----
For each test case, output a single line containing the number M or -1 as described above.

-----Constraints-----
- 1 ≤ T ≤ 5000
- 1 ≤ N ≤ 230

-----Example-----
Input:
1
3

Output:
1

-----Explanation-----First Example :  M desired in the problem would be 1. As bitwise XOR of 1 and 2 is equal to 3.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
a = [2 ** x - 1 for x in range(1, 31)]
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif n in a:
		print(n // 2)
	else:
		print('-1')


try:
	t = int(input())
	while t > 0:
		n = int(input())
		if n == 1:
			print(2)
			continue
		if n // 2 ^ n // 2 + 1 == n:
			print(n // 2)
		else:
			print(-1)
		t -= 1
except:
	pass


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	else:
		arr = []
		i = 0
		while True:
			if 2 ** i <= n:
				arr.append(2 ** i)
				i += 1
			else:
				break
		flg = 0
		for i in arr:
			if i ^ i - 1 == n:
				flg = 1
				print(i - 1)
				break
		if not flg:
			print(-1)


import math

def binary(n):
	l = []
	flag = 0
	while n > 0:
		if n % 2 == 0:
			flag = 1
		l.append(n % 2)
		n = n // 2
	return (l, flag)
t = int(input())
for x in range(t):
	n = int(input())
	b = []
	(b, f) = binary(n)
	b.reverse()
	a = int(math.log2(n))
	if n == 1:
		print(2)
	elif f == 0:
		print(pow(2, a) - 1)
	else:
		print(-1)


def read():
	return input().strip()

def readint():
	return int(read())
t = readint()
for i in range(0, t):
	n = readint()
	if n == 1:
		print(2)
		continue
	if n % 2 == 0:
		print(-1)
	else:
		isFound = True
		for j in range(0, 32):
			if n == (1 << j) - 1:
				k = 1 << j - 1
				isFound = False
				print(str(k - 1))
				break
		if isFound:
			print(-1)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(2)
		continue
	temp = math.floor(math.log(n + 1, 2))
	if 2 ** temp == n + 1:
		print((n + 1) // 2 - 1)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
		continue
	l = n.bit_length()
	first = 1 << l - 1
	second = n ^ first
	if first - second == 1:
		print(second)
	else:
		print(-1)


import sys
input()
for num in sys.stdin:
	num = int(num.rstrip())
	if num == 1:
		print(2)
		continue
	if num & num + 1 == 0:
		print(num // 2)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif n + 1 & n == 0:
		print(n // 2)
	else:
		print(-1)


try:
	primes = ['1']
	for i in range(2, 31):
		primes.append(primes[0] * i)
	for _ in range(int(input())):
		given = int(input())
		if given == 1:
			print('2')
			continue
		x = bin(given)[2:]
		if x in primes:
			print(int('1' * (len(x) - 1), 2))
		else:
			print('-1')
except:
	pass


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif n % 2 == 0:
		print(-1)
	else:
		m = n
		while m > 1:
			m = m // 2
			if m % 2 == 0:
				print(-1)
				break
		else:
			print(n // 2)


for _ in range(int(input())):
	a = int(input())
	flag = 0
	r = 0
	if a == 1:
		print('2')
	elif a & a + 1 == 0:
		print(a // 2)
	else:
		print('-1')


for i in range(int(input())):
	n = int(input())
	t = -1
	for j in range(30):
		if n == 2 ** j - 1:
			t = j
			break
	if t == 1:
		print(2)
	elif t == -1:
		print(-1)
	else:
		print(2 ** (t - 1) - 1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	else:
		num_str = bin(n)
		count = 0
		for i in range(2, len(num_str)):
			if num_str[i] == '0':
				count += 1
		if count == 0:
			print(n - (n + 1) // 2)
		else:
			print(-1)


from sys import *
test = int(input())
for tt in range(test):
	n = int(input())
	t = -1
	for i in range(30):
		if n == 2 ** i - 1:
			t = i
			break
	if t == 1:
		print(2)
	elif t == -1:
		print(-1)
	else:
		print(2 ** (t - 1) - 1)


from random import randint

def create_test():
	a = [x for x in range(1, pow(2, 20) + 1)]
	print(len(a))
	for x in a:
		print(x)
	exit(0)

class Solution:

	def __init__(self):
		super().__init__()
		self.t = int(input())
		self.dp = dict()
		self.dp[1] = 2
		value = 1
		for i in range(2, 31):
			key = pow(2, i) - 1
			self.dp[key] = value
			value = key
		pass

	def solve(self):
		for _ in range(self.t):
			n = int(input())
			ans = -1
			if n & 1:
				if n in self.dp.keys():
					ans = self.dp[n]
			print(ans)
		pass

def debug():
	a = [x for x in range(1, 500, 2)]
	for x in a:
		ans = -1
		for i in range(0, x):
			if i ^ i + 1 == x:
				ans = i
				break
		if ans != -1:
			print('%d ans = %d' % (x, ans))
	exit(0)
p = Solution()
p.solve()
pass


t = int(input())
s = []
for i in range(31):
	s.append(2 ** i - 1)
for _ in range(t):
	n = int(input())
	if n == 1:
		print(2)
	elif n in s:
		print(n // 2)
	else:
		print(-1)


t = int(input())
for T in range(t):
	n = int(input())
	b = bin(n)[2:]
	if n == 1:
		print(2)
	elif '0' in b:
		print(-1)
	else:
		print((n - 1) // 2)


for t in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif n + 1 & n:
		print(-1)
	else:
		print(n >> 1)


d = {1: 0}
st = 1
prev = 1
while True:
	new = st + st + 1
	d[new] = prev
	prev = new
	st = new
	if st > 2 * 2 ** 30:
		break
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	else:
		try:
			print(d[n])
		except:
			print(-1)


try:
	import math
	t = int(input())
	for i in range(0, t):
		n = int(input())
		if n == 1:
			print(2)
		else:
			k = (n + 2 - 1) // 2
			if k + k - 1 == n and math.log(k, 2).is_integer() == True:
				print(k - 1)
			else:
				print(-1)
except:
	pass


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(2)
		continue
	if n & n + 1 == 0:
		x = (n + 1) // 2 - 1
		print(x)
	else:
		print(-1)


s = set()
for i in range(31):
	s.add(2 ** i - 1)
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif n in s:
		print(n // 2)
	else:
		print(-1)


for _ in range(int(input())):
	l = int(input())
	if l == 1:
		print(2)
		continue
	t_1 = list(bin(l)[2:])
	flag = 0
	for i in range(len(t_1) - 1, 0, -1):
		if flag == 1 and t_1[i] == '1':
			break
		if t_1[i] == t_1[i - 1] and t_1[i] == '1':
			continue
		else:
			flag = 1
	if flag == 1:
		print(-1)
		continue
	t_2 = t_1.count('1')
	t_3 = 2 ** (t_2 - 1) - 1
	print(t_3)


t = int(input())
for _ in range(t):
	n = int(input())
	if n == 1:
		print(2)
	else:
		x = '{0:0b}'.format(n)
		x = len(x)
		c = pow(2, x)
		if c - n == 1:
			print(n - pow(2, x - 1))
		else:
			print(-1)


T = int(input())
for tx in range(T):
	N = int(input())
	if N == 1:
		print(2)
	else:
		M = N // 2
		if M ^ M + 1 == N:
			print(M)
		else:
			print(-1)


for i in range(int(input())):
	N = int(input())
	binary = bin(N)[2:]
	if N == 1:
		print(2)
	elif '0' in binary:
		print(-1)
	else:
		print((N - 1) // 2)


a = list()
i = 0
while i <= 30:
	a.append(2 ** i - 1)
	i += 1
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print('2')
		continue
	if n not in a:
		print(-1)
	else:
		print(n // 2)


t = int(input())
ar = []
for i in range(0, 100):
	ar.append(15 * 2 ** i + 2 ** i - 1)
for j in range(0, t):
	n = int(input())
	if n == 3:
		print(1)
	elif n == 1:
		print(2)
	elif n == 7:
		print(3)
	elif (n in ar) == True:
		print(n // 2)
	else:
		print(-1)


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'

def is_2n(n):
	while n % 2 == 0:
		n //= 2
	return True if n == 1 else False
for _ in range(int(input())):
	N = int(input())
	if N == 1:
		print(2)
	elif is_2n(N + 1):
		print(N // 2)
	else:
		print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(-1)
		continue
	if n == 1:
		print(2)
		continue
	p = math.ceil(math.log2(n))
	if 2 ** p - 1 != n:
		print(-1)
		continue
	ans = 2 ** (p - 1) - 1
	print(ans)


for _ in range(int(input())):
	curr = int(input())
	if bin(curr)[2:].count('0') > 0:
		print(-1)
	else:
		print([curr // 2, 2][curr == 1])


def xor():
	n = int(input())
	a = bin(n)[2:]
	if a.count('0') == 0:
		if n == 1:
			print(2)
		else:
			print(n >> 1)
	else:
		print(-1)

def __starting_point():
	t = int(input())
	while t != 0:
		xor()
		t -= 1
__starting_point()


T = int(input())
for i in range(T):
	N = int(input())
	f = bin(N)[2:]
	if f.count('0') == 0:
		if N == 1:
			print(2)
		else:
			print(N >> 1)
	else:
		print(-1)


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(int(input())):
	n = int(input())
	m = n + 1
	if n == 1:
		print('2')
	elif isPowerOfTwo(m):
		print(n // 2)
	else:
		print('-1')


import math
for __ in range(int(input())):
	N = int(input())
	if N == 1:
		print(2)
	elif N % 2 == 0:
		print(-1)
	elif math.log2(N // 2 + 1) - int(math.log2(N // 2 + 1)) == 0.0:
		print(N // 2)
	else:
		print(-1)


T = int(input())
for i in range(T):
	N = int(input())
	b = bin(N)[2:]
	if N == 1:
		print(2)
	elif '0' in b:
		print(-1)
	else:
		print((N - 1) // 2)


t = int(input())
while t != 0:
	n = int(input())
	b = bin(n)[2:]
	if n == 1:
		print(2)
	elif '0' in b:
		print(-1)
	else:
		print((n - 1) // 2)
	t -= 1


import math
t = int(input())
for i in range(t):
	N = int(input())
	info1 = math.floor(math.log(N, 2))
	info2 = math.floor(math.log(N + 1, 2))
	if N != 2 ** info2 - 1:
		print(-1)
	elif N == 1:
		print(2)
	else:
		print(N - 2 ** info1)


mod = 1000000007
read_int = lambda : int(input().strip())
read_str = lambda : input().strip()
read_str_arr = lambda : input().strip().split()
read_int_arr = lambda : [int(x) for x in input().strip().split()]

def solve():
	N = read_int()
	if N == 1:
		ans = 2
	elif N & N + 1 == 0:
		ans = N >> 1
	else:
		ans = -1
	print(ans)
for _ in range(int(input())):
	solve()


from math import *
for j in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	else:
		z = pow(2, ceil(log(n, 2)))
		e = int(log(n, 2))
		if z == n + 1:
			print(2 ** e - 1)
		else:
			print(-1)


l = []
for k in range(2, 31):
	l.append(2 ** k - 1)
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
		continue
	if n in l:
		print(n // 2)
	else:
		print(-1)


import math

def poww(n):
	res = 1
	a = 2
	while n:
		if n & 1:
			res *= a
		a *= a
		n >>= 1
	return res
for n in [*open(0)][1:]:
	n = int(n)
	if n == 1:
		print(2)
	elif math.ceil(math.log2(n + 1)) == math.floor(math.log2(n + 1)):
		cnt = 0
		while n:
			n = n & n - 1
			cnt += 1
		print(poww(cnt - 1) - 1)
	else:
		print(-1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	if n == 1:
		print(2)
	elif n + 1 & n:
		print(-1)
	else:
		print(n >> 1)


a = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823]
t = int(input())
for _ in range(0, t):
	n = int(input())
	if n == 1:
		print('2')
	elif n in a:
		p = a.index(n) - 1
		print(a[p])
	else:
		print('-1')


def solve():
	n = int(input())
	a = bin(n)[2:]
	if a.count('0') == 0:
		if n == 1:
			print(2)
		else:
			print(n >> 1)
	else:
		print(-1)
t = int(input())
while t != 0:
	solve()
	t -= 1


T = int(input())
for i in range(T):
	n = int(input())
	if n == 1:
		print(2)
		continue
	if n // 2 ^ n // 2 + 1 == n:
		print(n // 2)
	else:
		print(-1)


import math
for ijk in range(0, int(input())):
	a = int(input())
	a = bin(a)[2:]
	if a == '1':
		print(2)
	elif '0' in a:
		print(-1)
	else:
		print(int(a[1:], 2))


import math

def log2(x):
	return math.log(x) / math.log(2)
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	else:
		j = math.floor(log2(n))
		j = pow(2, j)
		k = j ^ j - 1
		if k == n:
			print(j - 1)
		else:
			print(-1)


import math
t = int(input())
l = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647]
for i in range(t):
	n = int(input())
	if n in l:
		if n == 1:
			print(2)
		else:
			print(n // 2)
	else:
		print(-1)


import math
for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
	elif math.ceil(math.log2(n + 1)) == math.floor(math.log2(n + 1)):
		cnt = 0
		while n:
			n = n & n - 1
			cnt += 1
		print(2 ** (cnt - 1) - 1)
	else:
		print(-1)


times = int(input())
for i in range(0, times):
	num = int(input())
	if num == 1:
		print(2)
	else:
		numString = bin(num)
		count0 = 0
		for j in range(2, len(numString)):
			if numString[j] == '0':
				count0 += 1
		if count0 == 0:
			print(num - (num + 1) // 2)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
		continue
	if n // 2 ^ n // 2 + 1 == n:
		print(n // 2)
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	flag = 0
	if n == 1:
		print('2')
	else:
		for i in range(1, 31):
			if 2 ** i - 1 == n:
				flag = 1
				t = i
				break
		if flag == 0:
			print('-1')
		else:
			print(2 ** (t - 1) - 1)


for _ in range(int(input())):
	n = int(input())
	flag = 0
	if n == 1:
		print(2)
		continue
	for i in range(1, 31):
		ans = 1 << i
		if ans ^ ans - 1 == n:
			print(ans - 1)
			flag = 1
	if flag == 0:
		print(-1)


t = int(input())
while t:
	t -= 1
	n = int(input())
	bi = bin(n)[2:]
	c0 = bi.count('0')
	if c0:
		print('-1')
	elif n == 1:
		print('2')
	else:
		print(n // 2)


numb = []
for i in range(31):
	numb.append(str(2 ** i - 1))
for _ in range(int(input())):
	n = input()
	if n == '1':
		print(2)
	elif n in numb:
		print(int(n, 10) // 2)
	else:
		print(-1)


t = int(input())
for i in range(t):
	k = int(input())
	if k % 2 == 0:
		print(-1)
	elif k % 2 != 0:
		c = (k + 1) // 2
		if k == c ^ c - 1:
			if k != 1:
				print(c - 1)
			if k == 1:
				print(2)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	if n == 1:
		print('2')
	elif n % 2 == 0:
		print(-1)
	else:
		x = bin(n)[2:].count('0')
		if x == 0:
			ans = n // 2
			print(ans)
		else:
			print(-1)


def main():
	from sys import stdin, stdout
	inp = stdin.readline
	out = stdout.write
	res = []
	t = int(inp().strip())
	for i in range(t):
		n = int(inp().strip())
		x = n // 2
		if n == 1:
			res.append('2\n')
		elif x ^ x + 1 == n:
			res.append(str(x) + '\n')
		else:
			res.append('-1\n')
	for i in range(t):
		out(res[i])
main()


from math import log2
for t in range(int(input())):
	i = int(input())
	if i == 1:
		print(2)
	else:
		b = int(log2(i + 1))
		a = log2(i + 1)
		if a == b:
			print(int(i / 2))
		else:
			print('-1')


T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	if N == 1:
		ans.append(2)
	elif '0' not in bin(N)[2:]:
		ans.append(N // 2)
	else:
		ans.append(-1)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	for m in range(1, 30 + 1):
		x = 2 ** m ^ 2 ** m - 1
		y = 2 ** m ^ 2 ** m + 1
		if x == n:
			print(2 ** m - 1)
			break
		elif y == n:
			print(2 ** m)
			break
	else:
		print(-1)


t = int(input())
for i in range(t):
	flag = True
	n = int(input())
	if n == 1:
		print(2)
	else:
		m = int(n / 2)
		if m ^ m + 1 == n:
			print(m)
		else:
			print(-1)


for _ in range(int(input())):
	n = int(input())
	(i, a) = (1, 0)
	if n == 1:
		print(2)
	else:
		while 2 ** i <= n + 1:
			if n == 2 ** i - 1:
				a = 1
				break
			i += 1
		if a == 1:
			print(n // 2)
		else:
			print(-1)


valid_n = [2 ** i - 1 for i in range(1, 31)]
T = int(input())
for tx in range(T):
	N = int(input())
	if N == 1:
		print(2)
	elif N in valid_n:
		print(valid_n[valid_n.index(N) - 1])
	else:
		print(-1)


t = int(input())
while t:
	n = int(input())
	if n == 1:
		ans = 2
	else:
		p = n
		p += 1
		flag = 0
		while p > 1:
			if p % 2 == 1:
				flag = 1
			p = p / 2
		if flag == 0:
			k = bin(n)[2:].count('1')
			ans = 2 ** (k - 1) - 1
		else:
			ans = -1
	print(ans)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	if n == 1:
		print(2)
	else:
		q = 0
		for i in range(1, 31):
			p = 1 << i
			if p ^ p - 1 == n:
				print(p - 1)
				q = 1
				break
		if q == 0:
			print(-1)
	t -= 1


t = int(input())
while t:
	n = int(input())
	if n == 1:
		print(2)
		t -= 1
		continue
	if n % 2 == 0:
		print(-1)
		t = t - 1
		continue
	idx = -1
	for i in range(0, 31):
		if pow(2, i) > n:
			if pow(2, i) - 1 == n:
				idx = n // 2
			break
	print(idx)
	t -= 1