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

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:
		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)
	elif 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 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)
	elif 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))


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

def num_shuff(w_a, w_b, c):
	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):
	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 = {}
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))