Chef likes to solve difficult tasks. This time, he tried to solve the Big Famous Unsolvable $A+B=C$. One of his friends played a prank on Chef and randomly shuffled the bits in $A$ and $B$ (independently in each number). However, the funny thing is that the sum of the resulting numbers remained $C$ even after shuffling.
Chef is now wondering: in how many ways is it possible to shuffle the bits of $A$ and the bits of $B$ such that their sum after shuffling is equal to $C$? Let's denote the integers obtained by shuffling the bits of $A$ and $B$ by $A_s$ and $B_s$ respectively; two ways $(A_{s1}, B_{s1})$ and $(A_{s2}, B_{s2})$ are considered distinct if $A_{s1} \neq A_{s2}$ or $B_{s1} \neq B_{s2}$.
It is allowed to add any number (possibly zero) of leading zeroes, i.e. bits $0$, to $A$ and any number of leading zeroes to $B$ before shuffling the bits.

-----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 $A$, $B$ and $C$. 

-----Output-----
For each test case, print a single line containing one integer — the number of ways to shuffle the bits.

-----Constraints-----
- $1 \le T \le 1,000$
- $1 \le A, B, C \le 10^9$
- $A+B = C$

-----Subtasks-----
Subtask #1 (50 points): $1 \le A, B, C \le 10^5$
Subtask #2 (50 points): original constraints

-----Example Input-----
2
1 2 3
369 428 797

-----Example Output-----
2
56

-----Explanation-----
Example case 1: We can consider $A=01$ and $B=10$ in binary. Then, there are two possible ways: swapping the two bits of $A$ and the two bits of $B$ ($A_s=10$, $B_s=01$ in binary, $2$ and $1$ in decimal representation) or not shuffling any bits.

Difficulty: interview

Starter code:

Solutions:
import math
def csb(n): 
 count = 0
 while (n): 
  n &= (n-1) 
  count+= 1
  
 return count
def f(ca,cb,i,cf,C,n,dp):
 if ca<0 or cb<0:
  return 0
 if i==n:
  if ca==0 and cb==0 and cf==0:
   return 1
  return 0
 st=str(ca)+" "+str(cb)+" "+str(cf)+" "+str(i)
 if dp.get(st)!=None:
  return dp[st]
 x=0 
 if (C&(1<<i))>0:
  x=1
 if x==1:
  #we will have odd num of set bits
  if cf==1:
   dp[st]=f(ca,cb,i+1,0,C,n,dp)+f(ca-1,cb-1,i+1,1,C,n,dp)
  else:
   dp[st]=f(ca-1,cb,i+1,0,C,n,dp)+f(ca,cb-1,i+1,0,C,n,dp)
 else:
  if cf==1:
   dp[st]=f(ca-1,cb,i+1,1,C,n,dp)+f(ca,cb-1,i+1,1,C,n,dp)
  else:
   dp[st]=f(ca,cb,i+1,0,C,n,dp)+f(ca-1,cb-1,i+1,1,C,n,dp)
   
 return dp[st]
def ip():
  
 for _ in range(int(input())):
  a,b,c=list(map(int,input().split()))
  n=int(math.log(c,2))+1
  dp={}
  print(f(csb(a),csb(b),0,0,c,n,dp))
ip()


import math
def csb(n): 
 count = 0
 while (n): 
  n &= (n-1) 
  count+= 1
  
 return count
def f(ca,cb,i,cf,C,n,dp):
 if ca<0 or cb<0:
  return 0
 if i==n:
  if ca==0 and cb==0 and cf==0:
   return 1
  return 0
 st=str(ca)+" "+str(cb)+" "+str(cf)+" "+str(i)
 if dp.get(st)!=None:
  return dp[st]
 x=0 
 if (C&(1<<i))>0:
  x=1
 if x==1:
  #we will have odd num of set bits
  if cf==1:
   dp[st]=f(ca,cb,i+1,0,C,n,dp)+f(ca-1,cb-1,i+1,1,C,n,dp)
  else:
   dp[st]=f(ca-1,cb,i+1,0,C,n,dp)+f(ca,cb-1,i+1,0,C,n,dp)
 else:
  if cf==1:
   dp[st]=f(ca-1,cb,i+1,1,C,n,dp)+f(ca,cb-1,i+1,1,C,n,dp)
  else:
   dp[st]=f(ca,cb,i+1,0,C,n,dp)+f(ca-1,cb-1,i+1,1,C,n,dp)
   
 return dp[st]
for _ in range(int(input())):
 a,b,c=list(map(int,input().split()))
 n=int(math.log(c,2))+1
 dp={}
 print(f(csb(a),csb(b),0,0,c,n,dp))



import numpy as np
N = 32;

def calc(i, na, nb, isOne):
 if na < 0 or nb < 0: return 0
 if i == len(c): return not na and not nb and not isOne
 ret = dp[i, na, nb, int(isOne)]

 if ret != -1: return ret
 ret = 0

 if isOne:
  if c[i] == '0':
   ret += calc(i+1, na-1, nb, True)
   ret += calc(i+1, na, nb-1, True)
  else:
   ret += calc(i+1, na, nb, False)
   ret += calc(i+1, na-1, nb-1, True)
 else:
  if c[i] == '0':
   ret += calc(i+1, na, nb, False);
   ret += calc(i+1, na-1, nb-1, True)
  else:
   ret += calc(i+1, na-1, nb, False)
   ret += calc(i+1, na, nb-1, False)

 dp[i, na, nb, int(isOne)] = ret
 return ret


t = int(input())
dp = np.array([-1] * N * N * N * 2).reshape(N, N, N, 2)
for _ in range(t):
 a, b, c = list(map(int, input().split()))
 c = "{0:b}".format(c)[::-1]
 x = "{0:b}".format(a).count('1')
 y = "{0:b}".format(b).count('1')
 dp.fill(-1)
 print(calc(0, x, y, False))


import numpy as np
N = 32;

def calc(i, na, nb, isOne):
 if na < 0 or nb < 0: return 0
 if i == len(c): return not na and not nb and not isOne
 ret = dp[i][na][nb][int(isOne)]

 if ret != -1: return ret
 ret = 0

 if isOne:
  if c[i] == '0':
   ret += calc(i+1, na-1, nb, True)
   ret += calc(i+1, na, nb-1, True)
  else:
   ret += calc(i+1, na, nb, False)
   ret += calc(i+1, na-1, nb-1, True)
 else:
  if c[i] == '0':
   ret += calc(i+1, na, nb, False);
   ret += calc(i+1, na-1, nb-1, True)
  else:
   ret += calc(i+1, na-1, nb, False)
   ret += calc(i+1, na, nb-1, False)

 dp[i][na][nb][int(isOne)] = ret
 return ret


t = int(input())
dp = np.array([-1] * N * N * N * 2).reshape(N, N, N, 2)
for _ in range(t):
 a, b, c = map(int, input().split())
 c = "{0:b}".format(c)[::-1]
 x = "{0:b}".format(a).count('1')
 y = "{0:b}".format(b).count('1')
 dp.fill(-1)
 print(calc(0, x, y, False))

import numpy as np
N = 32;

def calc(i, na, nb, isOne):
 if na < 0 or nb < 0: return 0
 if i == len(c): return not na and not nb and not isOne
 ret = dp[i][na][nb][int(isOne)]

 if ret != -1: return ret
 ret = 0

 if isOne:
  if c[i] == '0':
   ret += calc(i+1, na-1, nb, True)
   ret += calc(i+1, na, nb-1, True)
  else:
   ret += calc(i+1, na, nb, False)
   ret += calc(i+1, na-1, nb-1, True)
 else:
  if c[i] == '0':
   ret += calc(i+1, na, nb, False);
   ret += calc(i+1, na-1, nb-1, True)
  else:
   ret += calc(i+1, na-1, nb, False)
   ret += calc(i+1, na, nb-1, False)

 dp[i][na][nb][int(isOne)] = ret
 return ret


t = int(input())
for _ in range(t):
 a, b, c = list(map(int, input().split()))
 c = "{0:b}".format(c)[::-1]
 x = "{0:b}".format(a).count('1')
 y = "{0:b}".format(b).count('1')
 dp = np.array([-1] * N * N * N * 2).reshape(N, N, N, 2)
 print(calc(0, x, y, False))


def ham(x):
 w = 0
 while x:
  w += 1
  x &= x-1
 return w


def num_shuff(w_a, w_b, c):
 #known = {}
 if w_a < 0 or w_b < 0:
  return 0
 if c == 0:
  if w_a == 0 and w_b == 0:
   return 1
  else: 
   return 0
 if (w_a, w_b, c) in known:
  return known[(w_a, w_b, c)]
 c0 = c % 2
 c1 = c >> 1
 res = 0 
 if c0 == 0:
  res += num_shuff(w_a, w_b , c1 ) 
  res += num_shuff(w_a - 1, w_b - 1, c1 - 1 ) 
 else:
  res += num_shuff(w_a - 1, w_b, c1 )
  res += num_shuff(w_a, w_b - 1, c1 ) 
 known[(w_a, w_b, c)] = res
 return res


t = int(input())
known = {}
for _ in range(t):
 a, b, c = list(map(int, input().split()))
 print(num_shuff(ham(a), ham(b), c))


def ham(x):
 w = 0
 while x:
  w += 1
  x &= x-1
 return w


def num_shuff(w_a, w_b, c):
 #known = {}
 if w_a < 0 or w_b < 0:
  return 0
 if c == 0:
  if w_a == 0 and w_b == 0:
   return 1
  else: 
   return 0
 if (w_a, w_b, c) in known:
  return known[(w_a, w_b, c)]
 c0 = c % 2
 c1 = c >> 1
 res = 0 
 if c0 == 0:
  res += num_shuff(w_a, w_b , c1 ) 
  res += num_shuff(w_a - 1, w_b - 1, c1 - 1 ) 
 else:
  res += num_shuff(w_a - 1, w_b, c1 )
  res += num_shuff(w_a, w_b - 1, c1 ) 
 known[(w_a, w_b, c)] = res
 return res


t = int(input())
known = {}
for _ in range(t):
 a, b, c = list(map(int, input().split()))
 print(num_shuff(ham(a), ham(b), c))


from sys import stdin

def ham(x):
 w = 0
 while x:
  w += 1
  x &= x-1
 return w


def num_shuff(w_a, w_b, c):
 #known = {}
 if w_a < 0 or w_b < 0:
  return 0
 if c == 0:
  if w_a == 0 and w_b == 0:
   return 1
  else: 
   return 0
 if (w_a, w_b, c) in known:
  return known[(w_a, w_b, c)]
 c0 = c % 2
 c1 = c >> 1
 res = 0 
 if c0 == 0:
  res += num_shuff(w_a, w_b , c1 ) 
  res += num_shuff(w_a - 1, w_b - 1, c1 - 1 ) 
 else:
  res += num_shuff(w_a - 1, w_b, c1 )
  res += num_shuff(w_a, w_b - 1, c1 ) 
 known[(w_a, w_b, c)] = res
 return res


t = int(stdin.readline().strip())
known = {}
#abcs = []
for _ in range(t):
 a, b, c = list(map(int, stdin.readline().strip().split()))
 print(num_shuff(ham(a), ham(b), c))


from sys import stdin
from math import log2, floor

def ham(x):
 w = 0
 while x:
  w += 1
  x &= x-1
 return w


def num_shuff(w_a, w_b, c):
 #known = {}
 if w_a < 0 or w_b < 0:
  return 0
 if c == 0:
  if w_a == 0 and w_b == 0:
   return 1
  else: 
   return 0
 if (w_a, w_b, c) in known:
  return known[(w_a, w_b, c)]
 c0 = c % 2
 c1 = c >> 1
 res = 0 
 if c0 == 0:
  res += num_shuff(w_a, w_b , c1 ) 
  res += num_shuff(w_a - 1, w_b - 1, c1 - 1 ) 
 else:
  res += num_shuff(w_a - 1, w_b, c1 )
  res += num_shuff(w_a, w_b - 1, c1 ) 
 known[(w_a, w_b, c)] = res
 return res


t = int(stdin.readline().strip())
known = {}
#abcs = []
for _ in range(t):
 a, b, c = list(map(int, stdin.readline().strip().split()))
 print(num_shuff(ham(a), ham(b), c))


import math as ma
import sys
from decimal import Decimal as dec
from itertools import permutations

def li():
 return list(map(int , input().split()))

def num():
 return map(int , input().split())

def nu():
 return int(input())

def find_gcd(x , y):
 while (y):
  x , y = y , x % y
 return x

def ans(index,seta,setb,carry):
 if(seta<0 or setb<0):
  return 0
 if(index==inc):
  if(carry==0 and seta==0 and setb==0):
   return 1
  else:
   return 0
 if(dp[index][seta][setb][carry]!=-1):
  return dp[index][seta][setb][carry]
 z=int(sc[index])
 res=0
 if(carry==z):
  res+=ans(index+1,seta,setb,carry//2)
  res += ans(index + 1 , seta-1 , setb-1 , (2+carry)//2)
 if((1+carry)%2==z):
  res += ans(index + 1 , seta-1 , setb , (1+carry)//2)
  res += ans(index + 1 , seta , setb-1 , (1+carry)//2)
 dp[index][seta][setb][carry]=res
 return res

t=nu()
for it in range(t):
 a,b,c=num()
 sa=str(bin(a))[2:]
 sb=str(bin(b))[2:]
 zc=str(bin(c))[2:]
 ca=sa.count("1")+1
 cb=sb.count("1")+1
 cc=zc.count("1")+1
 inc=len(zc)
 sc=zc[::-1]
 dp=[-1]*inc
 for i in range(inc):
  dp[i]=[-1]*ca
  for j in range(ca):
   dp[i][j]=[-1]*cb
   for k in range(cb):
    dp[i][j][k]=[-1]*2
 print(ans(0,ca-1,cb-1,0))