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: interview

Starter code:

Solutions:
# from math import log2
# N = 10000
# for i in range(1,N):
#     # print(i)
#     for m in range(i):
#         if( (m^(m+1))==i ):
#             print(i)
#             print(m,m+1,bin(m)[2:])
#             print()
#             break
#     # else:
#         # print(-1)
#         # print()
T = int(input())
ans = []

for _ in range(T):
 N = int(input())

 # x = log2(N+1)
 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)

# cook your dish here
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)
 else:
  if n in s:
   print(n//2)
  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)
 else:
  if n in s:
   print(n//2)
  else:print(-1)

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

# cook your dish here
import math
for _ in range(int(input())):
 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)


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)


# cook your dish here
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()

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)


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

__starting_point()

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())
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

# cook your dish here
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)

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

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 _ 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')

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")
 else:
  if isPowerOfTwo(m):
   print(n//2)
  else:
   print("-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)

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


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


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

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

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)


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)


# cook your dish here
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)