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