You are given three non-negative integers $X$, $Y$ and $N$. Find the number of integers $Z$ such that $0 \le Z \le N$ and $(X \oplus Z) < (Y \oplus Z)$, where $\oplus$ denotes the bitwise XOR operation.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains three space-separated integers $X$, $Y$ and $N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of integers $Z$ which satisfy all conditions.

-----Constraints-----
- $1 \le T \le 1,000$
- $0 \le X, Y, N \le 2^{30} - 1$

-----Subtasks-----
Subtask #1 (5 points): $X, Y, N \le 2^6 - 1$
Subtask #2 (95 points): original constraints

-----Example Input-----
3
1 2 10
2 1 10
0 0 7

-----Example Output-----
6
5
0

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
tc=int(input())
for j in range(tc):
 ip=list(map(int,input().rstrip().split()))
 x=ip[0]
 y=ip[1]
 n=ip[2]
 cnt=0
 if(x==y):
  print('0')
  continue
 ln=bin(x).replace("0b", "") 
 rn=bin(y).replace("0b", "") 
 ll=len(ln)
 rl=len(rn)
 #print(ln)
 #print(rn)
 if(ll==len(rn)):
  for i in range(ll):
   
   if(ln[i]!=rn[i]):
    ln=ln[i:]
    rn=rn[i:]
    break
 #print(ln)
 if(ln[0]=='0'):
  ln=ln[1:]
  ll-=1
 #print(rn)
 if(rn[0]=='0'):
  rn=rn[1:]
  rl-=1
 ll=len(ln)
 rl=len(rn)
 if(ll>rl):
  lb=ll 
 else:
  lb=rl 
 pl=2**lb 
 hpl=pl//2
 amn=((n+1)//pl)*hpl 
 rm=(n+1)%pl 
 if((rm*2)<=pl):
  amn+=rm
 else:
  amn+=hpl 
 #print("amn = ",amn)
 aln=(n+1)-amn
 #print("aln = ",aln)
 if(x<y):
  print(amn)
 else:
  print(aln)

# cook your dish here
tc=int(input())
for j in range(tc):
 ip=list(map(int,input().rstrip().split()))
 x=ip[0]
 y=ip[1]
 n=ip[2]
 cnt=0
 if(x==y):
  print('0')
  continue
 ln=bin(x).replace("0b", "") 
 rn=bin(y).replace("0b", "") 
 ll=len(ln)
 rl=len(rn)
 #print(ln)
 #print(rn)
 if(ll==len(rn)):
  for i in range(ll):
   
   if(ln[i]!=rn[i]):
    ln=ln[i:]
    rn=rn[i:]
    break
 #print(ln)
 if(ln[0]=='0'):
  ln=ln[1:]
  ll-=1
 #print(rn)
 if(rn[0]=='0'):
  rn=rn[1:]
  rl-=1
 ll=len(ln)
 rl=len(rn)
 if(ll>rl):
  lb=ll 
 else:
  lb=rl 
 pl=2**lb 
 hpl=pl//2
 amn=((n+1)//pl)*hpl 
 rm=(n+1)%pl 
 if((rm*2)<=pl):
  amn+=rm
 else:
  amn+=hpl 
 #print("amn = ",amn)
 aln=(n+1)-amn
 #print("aln = ",aln)
 if(x<y):
  print(amn)
 else:
  print(aln)

# cook your dish here
tc=int(input())
for j in range(tc):
 ip=list(map(int,input().rstrip().split()))
 x=ip[0]
 y=ip[1]
 n=ip[2]
 cnt=0
 for i in range(n+1):
  if((x^i)<(y^i)):
   cnt+=1 
 print(cnt)

for _ in range(int(input())):
 x,y,n=map(int,input().split())
 c=0
 for i in range(n+1):
  if x^i<y^i:
   c=c+1
 print(c)

t = int(input())
for i in range(t):
 x,y,n = [int(i) for i in input().split()]
 
 bx = list(bin(x))
 by = list(bin(y))
 bx.remove(bx[0])
 bx.remove(bx[0])
 by.remove(by[0])
 by.remove(by[0])
 lx = len(bx)
 ly = len(by)
 index = 0
 flag = 2
 k = -1
 if(lx!= ly):
  index = max(lx,ly)
  #print(index)
  if((n+1)%2**(index) >= 2**(index-1)) :
   k = 2**(index-1)
  else :
   k =( n+1)%(2**(index))
  
  if(lx<ly):
   print(int((n+1)/2**index)*(2**(index-1)) + k) 
  else:
   print(n+1 - (int((n+1)/2**index)*(2**(index-1)) + k))
   
 else:
  
  for j in range(lx):
   if(bx[j]!= by[j]):
    index = lx-j
    if(bx[j] == '0'):
     flag = 0
    else:
     flag = 1
    break
  #  print(index)
  if((n+1)%2**(index) >= 2**(index-1)) :
   k = 2**(index-1)
  else :
   k =( n+1)%(2**(index))
  if(flag == 2) :
   print(0)
  elif(flag == 1):
   print(n+1 - (int((n+1)/2**index)*(2**(index-1)) + k))
  else:
   print(int((n+1)/2**index)*(2**(index-1)) + k) 
 
  
# for 0
# if((n+1)%2**(index) >= 2**(index-1)) : k = 2**(index-1)
# else :k =( n+1)%(2**(index))
#
# (int(n+1)/2**index)*(2**(index-1) + k
#
  


testcases = int(input())
for testcase in range(testcases):
 temparr = input()
 temparr = temparr.split()
 x = int(temparr[0])
 y = int(temparr[1])
 n = int(temparr[2])
 if x == y:
  print(0)
  continue
 diffbit = 0 
 biggestnum = 1<<5
 #print(biggestnum)
 checknum = 0 
 flag = 0 
 while True:
  curx = x & biggestnum
  cury = y & biggestnum
  if curx == cury:
   biggestnum = biggestnum >> 1 
   continue 
  checknum = biggestnum
  if curx:
   flag = 1 
  break 
 ans = 0 
 for i in range(n + 1):
  if flag == 1 :
   if i & checknum:
    ans += 1 
  else:
   if i & checknum == 0 :
    ans += 1 
 print(ans)
  
  
  


testcases = int(input())
for testcase in range(testcases):
 temparr = input()
 temparr = temparr.split()
 x = int(temparr[0])
 y = int(temparr[1])
 n = int(temparr[2])
 if x == y:
  print(0)
  continue
 binaryx= "{0:b}".format(x)
 binaryy = "{0:b}".format(y)
 nx = len(binaryx)
 ny = len(binaryy)
 maxlen = max(nx, ny)
 binaryx = (maxlen - nx) *"0" + binaryx
 binaryy = (maxlen - ny) *"0" + binaryy
 # print(binaryx)
 # print(binaryy)
 binaryn= "{0:b}".format(n)
 index = 0 
 flag = 0 
 # print(binaryx)
 # print(binaryy)
 for i in range(maxlen):
  if binaryx[i] == binaryy[i]:
   continue 
  index = i 
  if binaryy[i] == "0":
   flag = 1 
   break 
  
  break
 arr = []
 for i in range(maxlen):
  if i == index:
   arr.append("1")
  else:
   arr.append("0")
 newstrs = "".join(arr)
 compareresult = int(newstrs, 2)
 # print("index " + str(index))
 # print("compareresult " + str(compareresult))
 ans = 0 
 for i in range(n + 1):
  if flag == 1 and ( i & compareresult ):
   ans += 1 
  if flag == 0 and ( i & compareresult == 0):
   ans += 1 
 
 print(ans)
 
 
 
 
 
 


for _ in range(int(input())):
 [x,y,n] = list(map(int , input().split()))
 
 if (x==y):
  print(0)
 else:
  sn = bin(n)[2:]
  ln = len(sn)

  sx = bin(x)[2:]
  lx = len(sx)

  sy = bin(y)[2:]
  ly = len(sy)

  l = max(ln,lx,ly)
  
  sn = '0'*(l-ln) + sn
  sx = '0'*(l-lx) + sx
  sy = '0'*(l-ly) + sy

  for i in range(l):
   if (sx[i] != sy[i]):
    break
  #print("i = ",i)

  if (i == 0):
   t1 = 1
  else:
   t1 = int(sn[:i],2)+1

  rstval = 2**(l-i-1)

  #no limits
  if (sx[i] == '0' and sn[i] == '1'):
   print(t1 * rstval)
  
  elif (sx[i] == '1' and sn[i] == '1'):
   #print(256)
   if (i == l-1):
    t2 = 1
   else:
    t2 = int(sn[i+1:],2)+1
   print(t2 + (t1-1)*rstval)

  elif (sx[i] == '1' and sn[i] == '0'):
   t2 = rstval
   print((t1-1)*t2)

  #limits
  else:
   if (i == l-1):
    t2 = 1
   else:
    t2 = int(sn[i+1:],2)+1
   print(t2 + (t1-1)*rstval)

from random import randint

f = input

# f = open("in.txt", "r").readline


def din(st):
 return bin(st)[2:].zfill(10)


def func(x, y, n):
 # count = 0
 # for z in range(0, n+1):
 #     print(din(x), "xor", din(z), end=" ")
 #     if x ^ z < y ^ z:
 #         count += 1
 #         print("<", end=" ")
 #     else:
 #         print(">=", end="")
 #     print(din(y), "xor", din(z), "z =", z)
 z0 = x ^ 0 < y ^ 0
 unmatch = 1
 # print(z0)
 # print(x ^ unmatch < y ^ unmatch)
 while z0 == (x ^ unmatch < y ^ unmatch) and unmatch < n+1:
  # print(unmatch < n+1)
  unmatch *= 2
  # print("unmatch =", unmatch)
 # print("x y =", x, y)
 # print("unmatch =", unmatch)
 # print("n =", n)
 ans = ((n+1) // (unmatch*2)) * unmatch
 ans += min(unmatch, (n+1)-(ans*2))
 # print("ans =", ans)
 return (ans if z0 else ((n+1)-ans))


for _ in range(int(f())):
 x, y, n = list(map(int, f().split()))
 # x, y = (randint(1, 20), randint(1, 20))
 print(func(x, y, n))


# cook your dish here
a = int(input())
for i in range(a):
 b = list(map(int,str(input()).split(' ')))
 Ans = 0
 for i1 in range(b[2]+1):
  if (b[0]^i1)<(b[1]^i1):
   Ans+=1
 print(Ans)

for t in range(int(input())):
 x,y,n=map(int,input().split())
 n+=1
 count=0
 flag=0
 for i in range(29,-1,-1):
  if flag==0:
   if(x & (1<<i)) != (y & (1<<i)):
    for k in range(29,-1,-1):
     if (n & (1<<k)):
      if k>i:
       count+=(1<<(k-1))
      elif k==i:
       if (x & (1<<i))==0:
        count+=(1<<k)
      else:
       if (x & (1<<i)) == (n & (1<<i)):
        count+=(1<<k)
    flag=1
 print(count)

for t in range(int(input())):
 x,y,n=map(int,input().split())
 n+=1
 count=0
 flag=0
 for i in range(28,-1,-1):
  if flag==0:
   if(x & (1<<i)) != (y & (1<<i)):
    for k in range(28,-1,-1):
     if (n & (1<<k)):
      if k>i:
       count+=(1<<(k-1))
      elif k==i:
       if (x & (1<<i))==0:
        count+=(1<<k)
      else:
       if (x & (1<<i)) == (n & (1<<i)):
        count+=(1<<k)
    flag=1
 print(count)

for t in range(int(input())):
 x,y,n=list(map(int,input().split()))
 count=0
 for i in range(n+1):
  if (x^i)<(y^i):
   count+=1
 print(count)


for _ in range(int(input())):
 x,y,n=list(map(int,input().split()))
 z=[]
 count=0
 for i in range(n+1):
  z.append(i)
 for j in range(len(z)):
  if((x^z[j])<(y^z[j])):
   count+=1
 print(count)


# cook your dish here
for _ in range(int(input())):
 c=0
 x,y,n=tuple(map(int,input().split()))
 for z in range(0,n+1):
  if x^z<y^z:
   c+=1
 print(c)

# cook your dish here
def optimized(x,y,n):
 if x==y:return 0
 p=(x^y).bit_length()
 diff=pow(2,p)
 n=n+1
 ans=(n//diff)*(diff//2)
 if x<y:
  return ans+ (n%diff if n%(diff) < diff//2 else (diff//2))
 else:
  return ans+ (n%diff -(diff//2) if n%(diff) > diff//2 else 0)
  
  
for test in range(int (input())):
  x,y,n=map(int,input().split())
  print(optimized(x,y,n))

# cook your dish here
for _ in range(int(input())):
 x,y,n = map(int,input().split())
 n+=1
 ans = 0
 are_same = True
 for j in range(29,-1,-1):
  if are_same:
   if (x & (1 << j) != (y & (1 << j))):
    for k in range(29,-1,-1):
     if j>k:
      if (n&(1<<k)):
       if (n&(1<<j) == (x&(1<<j))):
        ans+=(1<<k)
     elif j==k:
      if (n&(1<<k)):
       if (x&(1<<j) == 0):
        ans += (1<<k)
     else:
      if (n&(1<<k)):
       ans +=(1<<(k-1))
  if (x & (1<<j)!=(y&(1<<j))):
   are_same = False
 print(ans)

test=int(input())
for i in range(0,test):
 x,y,n=map(int,input().split())
 counter=0
 for i in range(0,n+1):
  n=x^i
  m=y^i
  if(m>n):
   counter=counter+1
 print(counter)

for _ in range(int(input())):
 x,y,n=list(map(int,input().split()))
 c=0
 for i in range(n+1):
  if((x^i)<(y^i)):
   c+=1
 print(c)


def XOR(x,y,n):
 c = 0
 for z in range(0,n+1):
  a = x^z
  b = y^z
  if(a < b):
   c+=1
 return c


T = int(input())
for t in range(T):
 x,y,n = map(int,input().split())
 result = XOR(x,y,n)
 print(result)

t = int(input())

for _ in range(t):
 x,y,n = list(map(int,input().split()))
 ct = 0
 for z in range(n+1):
  if (z^x)<(z^y):
   ct += 1
 print(ct)



# cook your dish here
 

for _ in range(int(input())) :
 x, y, n = map(int,input().split())
 counter = 0
 
 for i in range(n+1) :
  if x^i < y^i :
   counter += 1
   
 print(counter)

# cook your dish here
from random import randint

f = input

# f = open("in.txt", "r").readline


def din(st):
 return bin(st)[2:].zfill(10)


def func(x, y, n):
 # count = 0
 # for z in range(0, n+1):
 #     print(din(x), "xor", din(z), end=" ")
 #     if x ^ z < y ^ z:
 #         count += 1
 #         print("<", end=" ")
 #     else:
 #         print(">=", end="")
 #     print(din(y), "xor", din(z), "z =", z)
 z0 = x ^ 0 < y ^ 0
 unmatch = 1
 # print(z0)
 # print(x ^ unmatch < y ^ unmatch)
 while z0 == (x ^ unmatch < y ^ unmatch) and unmatch < n+1:
  # print(unmatch < n+1)
  unmatch *= 2
  # print("unmatch =", unmatch)
 # print("x y =", x, y)
 # print("unmatch =", unmatch)
 # print("n =", n)
 ans = ((n+1) // (unmatch*2)) * unmatch
 ans += min(unmatch, (n+1)-(ans*2))
 # print("ans =", ans)
 return (ans if z0 else ((n+1)-ans))


for _ in range(int(f())):
 x, y, n = list(map(int, f().split()))
 # x, y = (randint(1, 20), randint(1, 20))
 print(func(x, y, n))


# cook your dish here
n=int(input())
for _ in range(n):
 a,b,c=[int(i) for i in input().split()]
 l=list(range(0,c+1))
 d=0
 for i in range(0,len(l)):
  if((a^l[i])<(b^l[i])):
   d=d+1
 print(d)