Chef has 3 numbers P, Q and R. Chef wants to find the number of triples (A, B, C) such that:
(A \mid B) = P, (B \mid C) = Q and (C \mid A) = R (Here, \mid denotes the [bitwise OR operation]
0 ≤ A, B, C < 2^{20}

Can you help Chef?

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input containing 3 space-separated integers denoting P, Q and R respectively.

------ Output Format ------ 

For each test case, output a single integer denoting the number of triplets (A, B, C) that satisfy the given conditions.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$0 ≤ P, Q, R < 2^{20}$

----- Sample Input 1 ------ 
3
10 12 14
0 5 5
0 0 7

----- Sample Output 1 ------ 
4
1
0

----- explanation 1 ------ 
Test case $1$: The following $4$ triplets $(A, B, C)$ satisfy $A \mid B = 10, B\mid C = 12,$ and $C\mid A = 14$: $(2, 8, 12), (10, 0, 12), (10, 8, 4),$ and $(10, 8, 12)$.

Test case $2$: The following triplet $(A, B, C)$ satisfies $A \mid B = 0, B\mid C = 5,$ and $C\mid A = 5$: $(0, 0, 5)$.

Test case $3$: There are no triplets satisfying all the conditions.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Combinatorics

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	ans = 1
	res = [1, 0, 1, 4]
	for i in range(30):
		ans *= res[(p >> i & 1) + (q >> i & 1) + (r >> i & 1)]
	print(ans)


def check_zero(left, right, bit_r, l):
	for i in range(l):
		if len(bit_r) - 1 - i > 1:
			if bit_r[len(bit_r) - 1 - i] == '0':
				left[l - 1 - i] = 0
				right[l - 1 - i] = 0
		else:
			left[l - 1 - i] = 0
			right[l - 1 - i] = 0

def check_one(left, right, bit_r, l):
	for i in range(l):
		if left[l - 1 - i] + right[l - 1 - i] == -1:
			if (len(bit_r) - 1 - i > 1) & (bit_r[len(bit_r) - 1 - i] == '1'):
				if left[l - 1 - i] == -1:
					left[l - 1 - i] = 1
				if right[l - 1 - i] == -1:
					right[l - 1 - i] = 1
		if left[l - 1 - i] + right[l - 1 - i] == 0:
			if (len(bit_r) - 1 - i > 1) & (bit_r[len(bit_r) - 1 - i] == '1'):
				return False
	return True
t = int(input())
for i in range(t):
	(P, Q, R) = map(int, input().split())
	bit_P = bin(P)
	bit_Q = bin(Q)
	bit_R = bin(R)
	l = max(len(bit_P), len(bit_Q), len(bit_R)) - 2
	list_A = list((-1 for i in range(l)))
	list_B = list_A.copy()
	list_C = list_A.copy()
	check_zero(list_A, list_B, bit_P, l)
	check_zero(list_C, list_B, bit_Q, l)
	check_zero(list_A, list_C, bit_R, l)
	result = 0
	if all([check_one(list_A, list_B, bit_P, l), check_one(list_C, list_B, bit_Q, l), check_one(list_A, list_C, bit_R, l)]):
		result = 1
		for i in range(l):
			if all(list((clist[i] == -1 for clist in [list_A, list_B, list_C]))):
				result = result * 4
	print(result)


from collections import deque
case = int(input())
for _ in range(case):
	(p, q, r) = map(int, input().split(' '))
	one = 0
	two = 0
	three = 0
	while p > 0 or q > 0 or r > 0:
		csum = (p & 1) + (q & 1) + (r & 1)
		if csum == 1:
			one += 1
		elif csum == 2:
			two += 1
		elif csum == 3:
			three += 1
		p >>= 1
		q >>= 1
		r >>= 1
	if one == 0 and two == 0 and (three == 0):
		print(1)
		continue
	if one > 0:
		print(0)
		continue
	elif three == 0:
		print(1)
		continue
	elif three > 0:
		print(pow(4, three))
		continue


for _ in range(int(input())):
	lst0 = [int(x) for x in input().split()]
	lst1 = [0 for i in range(20)]
	for i in range(3):
		j = 0
		while lst0[i] > 0:
			lst1[j] += lst0[i] % 2
			j += 1
			lst0[i] //= 2
	ans = 1
	for i in range(20):
		if lst1[i] == 3:
			ans *= 4
		elif lst1[i] == 1:
			ans *= 0
	print(ans)


mat = {(0, 0, 0): 1, (0, 0, 1): 0, (0, 1, 0): 0, (0, 1, 1): 1, (1, 0, 0): 0, (1, 0, 1): 1, (1, 1, 0): 1, (1, 1, 1): 4}
t = int(input())
for _ in range(t):
	(p, q, r) = list(map(int, input().split()))
	ans = 1
	while p or q or r:
		x = p % 2
		y = q % 2
		z = r % 2
		ans *= mat[x, y, z]
		p //= 2
		q //= 2
		r //= 2
	print(ans)


T = int(input())
for _ in range(T):
	(P, Q, R) = map(int, input().split())
	poss = 1
	while P != 0 or Q != 0 or R != 0:
		bP = P & 1
		bQ = Q & 1
		bR = R & 1
		btcnt = 0
		if bP:
			if bQ and bR:
				btcnt += 2
			if bQ:
				btcnt += 1
			if bR:
				btcnt += 1
		elif bQ == bR:
			btcnt += 1
		P = P >> 1
		Q = Q >> 1
		R = R >> 1
		poss *= btcnt
	print(poss)


T = int(input())
for temp in range(T):
	(P, Q, R) = map(int, input().split())
	All = P | Q | R
	a = All ^ Q
	b = All ^ R
	c = All ^ P
	common = All ^ a ^ b ^ c
	A = a | common
	B = b | common
	C = c | common
	if All != P | Q:
		output = 0
	elif All != Q | R:
		output = 0
	elif All != R | P:
		output = 0
	else:
		output = 4 ** bin(common).count('1')
	print(output)


t = int(input())
for _ in range(t):
	(p, q, r) = map(int, input().split())
	cnt = 0
	while p or q or r:
		(pd, qd, rd) = (p % 2, q % 2, r % 2)
		sm = pd + qd + rd
		if sm == 3:
			cnt += 2
		elif sm == 1:
			cnt = -1
			break
		p //= 2
		q //= 2
		r //= 2
	if cnt == -1:
		print(0)
	else:
		print(2 ** cnt)


for _ in range(int(input())):
	(AVB, BVC, AVC) = map(int, input().split())
	multiplier = 1
	for j in range(20):
		currentBit = 2 ** (20 - j - 1)
		count = 0
		if AVB >= currentBit:
			AVB -= currentBit
			count += 1
		if BVC >= currentBit:
			BVC -= currentBit
			count += 1
		if AVC >= currentBit:
			AVC -= currentBit
			count += 1
		if count == 3:
			multiplier *= 4
		if count == 1:
			multiplier *= 0
			break
	print(multiplier)


for _ in range(int(input())):
	(P, Q, R) = list(map(int, input().split()))
	p = str(bin(P))[2:]
	q = str(bin(Q))[2:]
	r = str(bin(R))[2:]
	pl = len(p)
	ql = len(q)
	rl = len(r)
	ml = max(pl, ql, rl)
	p = '0' * (ml - pl) + p
	r = '0' * (ml - rl) + r
	q = '0' * (ml - ql) + q
	ans = 1
	flag = True
	for i in range(ml):
		if int(p[i]) + int(q[i]) + int(r[i]) == 1:
			flag = False
			break
		elif int(p[i]) + int(q[i]) + int(r[i]) == 3:
			ans *= 4
	if flag:
		print(ans)
	else:
		print(0)


POPCOUNT_TABLE10 = [0] * 2 ** 10
for index in range(len(POPCOUNT_TABLE10)):
	POPCOUNT_TABLE10[index] = (index & 1) + POPCOUNT_TABLE10[index >> 1]

def dpopcount20_table10(v):
	return POPCOUNT_TABLE10[v & 1023] + POPCOUNT_TABLE10[v >> 10 & 1023] << 1
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print(1 << dpopcount20_table10(a) if p ^ q ^ r == (a := (p & q & r)) else 0)


POPCOUNT_TABLE16 = [0] * 2 ** 16
for index in range(len(POPCOUNT_TABLE16)):
	POPCOUNT_TABLE16[index] = (index & 1) + POPCOUNT_TABLE16[index >> 1]

def popcount32_table16(v):
	return POPCOUNT_TABLE16[v & 65535] + POPCOUNT_TABLE16[v >> 16 & 65535]
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print(1 << 2 * popcount32_table16(a) if p ^ q ^ r == (a := (p & q & r)) else 0)


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print(1 << 2 * bin(a).count('1') if p ^ q ^ r == (a := (p & q & r)) else 0)


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print((1, 0, 1, 4)[(p & 1) + (q & 1) + (r & 1)] * (1, 0, 1, 4)[(p >> 1 & 1) + (q >> 1 & 1) + (r >> 1 & 1)] * (1, 0, 1, 4)[(p >> 2 & 1) + (q >> 2 & 1) + (r >> 2 & 1)] * (1, 0, 1, 4)[(p >> 3 & 1) + (q >> 3 & 1) + (r >> 3 & 1)] * (1, 0, 1, 4)[(p >> 4 & 1) + (q >> 4 & 1) + (r >> 4 & 1)] * (1, 0, 1, 4)[(p >> 5 & 1) + (q >> 5 & 1) + (r >> 5 & 1)] * (1, 0, 1, 4)[(p >> 6 & 1) + (q >> 6 & 1) + (r >> 6 & 1)] * (1, 0, 1, 4)[(p >> 7 & 1) + (q >> 7 & 1) + (r >> 7 & 1)] * (1, 0, 1, 4)[(p >> 8 & 1) + (q >> 8 & 1) + (r >> 8 & 1)] * (1, 0, 1, 4)[(p >> 9 & 1) + (q >> 9 & 1) + (r >> 9 & 1)] * (1, 0, 1, 4)[(p >> 10 & 1) + (q >> 10 & 1) + (r >> 10 & 1)] * (1, 0, 1, 4)[(p >> 11 & 1) + (q >> 11 & 1) + (r >> 11 & 1)] * (1, 0, 1, 4)[(p >> 12 & 1) + (q >> 12 & 1) + (r >> 12 & 1)] * (1, 0, 1, 4)[(p >> 13 & 1) + (q >> 13 & 1) + (r >> 13 & 1)] * (1, 0, 1, 4)[(p >> 14 & 1) + (q >> 14 & 1) + (r >> 14 & 1)] * (1, 0, 1, 4)[(p >> 15 & 1) + (q >> 15 & 1) + (r >> 15 & 1)] * (1, 0, 1, 4)[(p >> 16 & 1) + (q >> 16 & 1) + (r >> 16 & 1)] * (1, 0, 1, 4)[(p >> 17 & 1) + (q >> 17 & 1) + (r >> 17 & 1)] * (1, 0, 1, 4)[(p >> 18 & 1) + (q >> 18 & 1) + (r >> 18 & 1)] * (1, 0, 1, 4)[(p >> 19 & 1) + (q >> 19 & 1) + (r >> 19 & 1)])


from functools import reduce
from operator import mul
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print(((p & 1) + (q & 1) + (r & 1) - 1) ** 2 * ((p >> 1 & 1) + (q >> 1 & 1) + (r >> 1 & 1) - 1) ** 2 * ((p >> 2 & 1) + (q >> 2 & 1) + (r >> 2 & 1) - 1) ** 2 * ((p >> 3 & 1) + (q >> 3 & 1) + (r >> 3 & 1) - 1) ** 2 * ((p >> 4 & 1) + (q >> 4 & 1) + (r >> 4 & 1) - 1) ** 2 * ((p >> 5 & 1) + (q >> 5 & 1) + (r >> 5 & 1) - 1) ** 2 * ((p >> 6 & 1) + (q >> 6 & 1) + (r >> 6 & 1) - 1) ** 2 * ((p >> 7 & 1) + (q >> 7 & 1) + (r >> 7 & 1) - 1) ** 2 * ((p >> 8 & 1) + (q >> 8 & 1) + (r >> 8 & 1) - 1) ** 2 * ((p >> 9 & 1) + (q >> 9 & 1) + (r >> 9 & 1) - 1) ** 2 * ((p >> 10 & 1) + (q >> 10 & 1) + (r >> 10 & 1) - 1) ** 2 * ((p >> 11 & 1) + (q >> 11 & 1) + (r >> 11 & 1) - 1) ** 2 * ((p >> 12 & 1) + (q >> 12 & 1) + (r >> 12 & 1) - 1) ** 2 * ((p >> 13 & 1) + (q >> 13 & 1) + (r >> 13 & 1) - 1) ** 2 * ((p >> 14 & 1) + (q >> 14 & 1) + (r >> 14 & 1) - 1) ** 2 * ((p >> 15 & 1) + (q >> 15 & 1) + (r >> 15 & 1) - 1) ** 2 * ((p >> 16 & 1) + (q >> 16 & 1) + (r >> 16 & 1) - 1) ** 2 * ((p >> 17 & 1) + (q >> 17 & 1) + (r >> 17 & 1) - 1) ** 2 * ((p >> 18 & 1) + (q >> 18 & 1) + (r >> 18 & 1) - 1) ** 2 * ((p >> 19 & 1) + (q >> 19 & 1) + (r >> 19 & 1) - 1) ** 2)


from functools import reduce
from operator import mul
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print(reduce(mul, [((p >> b & 1) + (q >> b & 1) + (r >> b & 1) - 1) ** 2 for b in range(20)]))


from functools import reduce
from operator import mul
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	print((1, 0, 1, 4)[(p & 1) + (q & 1) + (r & 1)] * reduce(mul, [(1, 0, 1, 4)[((p := (p >> 1)) & 1) + ((q := (q >> 1)) & 1) + ((r := (r >> 1)) & 1)] for _ in range(19)]))


from functools import reduce
from operator import mul
for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	ans = (1, 0, 1, 4)[(p & 1) + (q & 1) + (r & 1)]
	for _ in range(20):
		if not ans:
			break
		ans *= (1, 0, 1, 4)[((p := (p >> 1)) & 1) + ((q := (q >> 1)) & 1) + ((r := (r >> 1)) & 1)]
	print(ans)


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	ans = 1
	while p or q or r:
		p1 = p & 1
		q1 = q & 1
		r1 = r & 1
		if p1 + q1 + r1 == 1:
			ans = 0
			break
		elif p1 + q1 + r1 == 3:
			ans *= 4
		p >>= 1
		q >>= 1
		r >>= 1
	print(ans)


def calculate(arr):
	p = arr[0]
	q = arr[1]
	r = arr[2]
	pbit = [0 for i in range(21)]
	qbit = [0 for i in range(21)]
	rbit = [0 for i in range(21)]
	i = 20
	while p > 0:
		rem = p % 2
		pbit[i] = rem
		p = p // 2
		i -= 1
	i = 20
	while q > 0:
		rem = q % 2
		qbit[i] = rem
		q = q // 2
		i -= 1
	i = 20
	while r > 0:
		rem = r % 2
		rbit[i] = rem
		r = r // 2
		i -= 1
	ans = 1
	for i in range(21):
		sumi = pbit[i] + qbit[i] + rbit[i]
		if sumi == 3:
			ans = ans * 4
		elif sumi == 2 or sumi == 0:
			ans = ans * 1
		else:
			return 0
	return ans
t = int(input())
for i in range(t):
	arr = list(map(int, input().split()))
	v = calculate(arr)
	print(v)


t = int(input())
for _ in range(t):
	(p, q, r) = map(int, input().split())
	ans = 1
	for i in range(20):
		mask = 1 << i
		count = 0
		count += mask & p != 0
		count += mask & q != 0
		count += mask & r != 0
		if count == 0:
			ans *= 1
		elif count == 1:
			ans *= 0
		elif count == 2:
			ans *= 1
		else:
			ans *= 4
	print(ans)


T = int(input())
for t in range(1, T + 1):
	ans = 1
	(P, Q, R) = map(int, input().split())
	for i in range(20):
		mask = 1 << i
		count = 0
		count += mask & P != 0
		count += mask & Q != 0
		count += mask & R != 0
		if count == 0:
			ans *= 1
		elif count == 1:
			ans *= 0
		elif count == 2:
			ans *= 1
		else:
			ans *= 4
	print(ans)


def countTriples(p, q, r):
	result = 1
	while p + q + r > 0:
		bitSum = (p & 1) + (q & 1) + (r & 1)
		if bitSum == 1:
			result *= 0
		elif bitSum == 3:
			result *= 4
		p //= 2
		q //= 2
		r //= 2
	return result
numTestCases = int(input())
for i in range(numTestCases):
	(p, q, r) = map(int, input().split(' '))
	print(countTriples(p, q, r))


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	ans = 1
	while a or b or c:
		a1 = a & 1
		b1 = b & 1
		c1 = c & 1
		if a1 + b1 + c1 == 1:
			ans = 0
			break
		elif a1 + b1 + c1 == 3:
			ans *= 4
		a >>= 1
		b >>= 1
		c >>= 1
	print(ans)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	ans = 1
	while l[0] or l[1] or l[2]:
		a = l[0] & 1
		b = l[1] & 1
		c = l[2] & 1
		if a + b + c == 1:
			ans = 0
			break
		elif a + b + c == 3:
			ans *= 4
		l[0] >>= 1
		l[1] >>= 1
		l[2] >>= 1
	print(ans)


import time
import sys
import math

def get_primes(n):
	sieve = [True] * n
	for i in range(3, int(n ** 0.5) + 1, 2):
		if sieve[i]:
			sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
	return [2] + [i for i in range(3, n, 2) if sieve[i]]
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
input = sys.stdin.readline
(mod, infi) = (1000000007, sys.maxsize)
from collections import deque, Counter, defaultdict as dd
from heapq import heappop, heappush, heapify
from itertools import accumulate
from functools import lru_cache, reduce
from operator import mul, add, sub, truediv, floordiv, lt, le, eq, ne, gt, xor, concat, getitem, lshift
inty = lambda : int(input())
stringy = lambda : input().strip()
normal = lambda : input().split()
mappy = lambda : map(int, input().strip().split())
fmappy = lambda : map(float, input().strip().split())
listy = lambda : list(map(int, input().strip().split()))
tick = lambda : time.perf_counter()
logg = lambda a, b: math.log2(a) / math.log2(b)
acc = lambda x: list(accumulate(x))
sign = lambda x, y: x >= 0 and y >= 0 or (x < 0 and y < 0)
T = inty()
for _ in range(T):
	(p, q, r) = mappy()
	res = 1
	for bit in range(20):
		cnt = (p >> bit & 1) + (q >> bit & 1) + (r >> bit & 1)
		if cnt == 1:
			res = 0
			break
		if cnt == 3:
			res *= 4
	print(res)


t = int(input())
for _ in range(t):
	(p, q, r) = list(map(int, input().split()))
	ans = 1
	d = 0
	for i in range(21):
		k = 0
		if p & 1 << i:
			k += 1
		if q & 1 << i:
			k += 1
		if r & 1 << i:
			k += 1
		if k == 3:
			ans *= 4
		elif k == 2:
			pass
		elif k == 1:
			d = 1
		else:
			pass
	if d == 0:
		print(ans)
	else:
		print(0)


ans = []
for _ in range(int(input())):
	N = [bin(int(x))[2:].rjust(20, '0') for x in input().split()]
	an = 1
	for i in range(20):
		s = ''.join((N[x][i] for x in range(3))).count('1')
		if s in [0, 2]:
			continue
		elif s == 3:
			an *= 4
		else:
			an = 0
			break
	ans.append(an)
print(*ans, sep='\n')


ans = []
for _ in range(int(input())):
	N = [bin(int(x))[2:] for x in input().split()]
	for i in range(3):
		N[i] = '0' * (20 - len(N[i])) + N[i]
	an = 1
	for i in range(20):
		s = sum((int(N[x][i]) for x in [0, 1, 2]))
		if s == 0 or s == 2:
			continue
		elif s == 3:
			an *= 4
		else:
			an = 0
			break
	ans.append(an)
print(*ans, sep='\n')


d_zeros = {3: 1, 2: 0, 1: 1, 0: 4}
for t in range(int(input())):
	(p, q, r) = [int(x) for x in input().split()]
	prod = 1
	for i in range(max(p, q, r).bit_length()):
		count = 0
		if int(p >> i & 1) == 0:
			count += 1
		if int(q >> i & 1) == 0:
			count += 1
		if int(r >> i & 1) == 0:
			count += 1
		prod *= d_zeros[count]
	print(prod)


import math
cases = int(input())
for _ in range(cases):
	(p, q, r) = (int(e) for e in input().split(' '))
	sols = 1
	while p or q or r:
		tot = (p & 1) + (q & 1) + (r & 1)
		if tot == 3:
			sols *= 4
		elif tot == 1:
			sols = 0
			break
		p >>= 1
		q >>= 1
		r >>= 1
	print(sols)


def count(a, b, c):
	s = a + b + c
	if s == 0:
		return 1
	elif s == 1:
		return 0
	elif s == 2:
		return 1
	else:
		return 4
t = int(input())
for test in range(t):
	(P, Q, R) = list(map(int, input().split()))
	Pb = list(map(int, bin(P)[2:]))
	Qb = list(map(int, bin(Q)[2:]))
	Rb = list(map(int, bin(R)[2:]))
	max_size = max(len(Pb), len(Qb), len(Rb))
	Pb = [0] * (max_size - len(Pb)) + Pb
	Qb = [0] * (max_size - len(Qb)) + Qb
	Rb = [0] * (max_size - len(Rb)) + Rb
	prod = 1
	for i in range(max_size):
		prod *= count(Pb[i], Qb[i], Rb[i])
		if prod == 0:
			break
	print(prod)


T = int(input())
for i in range(T):
	(P, Q, R) = map(int, input().split(' '))
	A = 1
	for j in range(30):
		C = (P >> j & 1) + (Q >> j & 1) + (R >> j & 1)
		if C == 1:
			A = 0
		elif C == 3:
			A *= 4
	print(A)


import collections
import heapq
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def valid(i, j, n, m):
	if i < n and i >= 0 and (j >= 0) and (j < m):
		return True
	return False

def sumn(i, n):
	return (n - i) * (i + n) / 2

def sqfun(a, b, c):
	return (-b + math.sqrt(b * b - 4 * a * c)) / 2 * a

def getprime(num):
	if all((num % i != 0 for i in range(2, int(math.sqrt(num)) + 1))):
		return True

def value():
	return tuple(map(int, input().split()))

def values():
	return tuple(map(int, sys.stdin.readline().split()))

def inlst():
	return [int(i) for i in input().split()]

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(input())

def inps():
	return int(sys.stdin.readline())

def instr():
	return input()

def stlst():
	return [i for i in input().split()]

def solve():
	(p, q, r) = values()
	mx = max(p, q, r)
	tot = 1
	for i in range(mx.bit_length()):
		(k, h, w) = (p & 1 << i, q & 1 << i, r & 1 << i)
		if k == 0 or h == 0 or w == 0:
			if k == 0 and h == w:
				continue
			if h == 0 and k == w:
				continue
			if w == 0 and h == k:
				continue
			return 0
		else:
			tot *= 4
	return tot
for i in range(inp()):
	print(solve())


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	ans = 1
	for bit in range(30):
		ct = (p >> bit & 1) + (q >> bit & 1) + (r >> bit & 1)
		if ct == 1:
			ans = 0
		elif ct == 3:
			ans *= 4
	print(ans)


def solve(p, q, r):
	(a, b, c) = (0, 0, 0)
	ans = 1
	for _ in range(20):
		(a, b, c) = (p % 2, q % 2, r % 2)
		k = [a, b, c].count(1)
		if k == 0:
			ans *= 1
		if k == 1:
			return 0
		if k == 2:
			ans *= 1
		if k == 3:
			ans *= 4
		p //= 2
		q //= 2
		r //= 2
	return ans
t = int(input())
for _ in range(t):
	(p, q, r) = list(map(int, input().split()))
	print(solve(p, q, r))


for i in range(int(input())):
	(x, y, z) = map(int, input().split())
	ans = 1
	for bit in range(20):
		ct = (x >> bit & 1) + (y >> bit & 1) + (z >> bit & 1)
		if ct == 1:
			ans = 0
		elif ct == 3:
			ans *= 4
	print(ans)


t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	ans = 1
	for bit in range(30):
		ct = (a >> bit & 1) + (b >> bit & 1) + (c >> bit & 1)
		if ct == 1:
			ans = 0
		if ct == 3:
			ans *= 4
	print(ans)


class T:

	def solve(self):
		(p, q, r) = map(int, input().split())
		ans = 1
		for i in range(64, -1, -1):
			a = 0
			if p & 1 << i:
				a += 1
			if r & 1 << i:
				a += 1
			if q & 1 << i:
				a += 1
			if a == 3:
				ans *= 4
			elif a == 2:
				continue
			elif a == 1:
				return 0
			else:
				continue
		return ans
for t in range(int(input())):
	obj = T()
	print(obj.solve())


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	a = [1, 0, 1, 4]
	answer = 1
	for i in range(30):
		answer *= a[(p >> i & 1) + (q >> i & 1) + (r >> i & 1)]
	print(answer)


t = int(input())
for _ in range(t):
	(p, q, r) = map(int, input().split())
	arr = [1, 0, 1, 4]
	ans = 1
	for i in range(20):
		x = p >> i & 1
		y = q >> i & 1
		z = r >> i & 1
		ans = ans * arr[x + y + z]
	print(ans, end=' ')
	print()


t = int(input())
for _ in range(t):
	(p, q, r) = map(int, input().split())
	a = [1, 0, 1, 4]
	ans = 1
	for j in range(30):
		x = p >> j & 1
		y = q >> j & 1
		z = r >> j & 1
		ans = ans * a[x + y + z]
	print(ans)


n = int(input())
for i in range(n):
	(p, q, r) = list(map(int, input().split()))
	a = [1, 0, 1, 4]
	ans = 1
	for j in range(30):
		x = p >> j & 1
		y = q >> j & 1
		z = r >> j & 1
		ans = ans * a[x + y + z]
	print(ans)


for _ in range(int(input())):
	(p, q, r) = list(map(lambda x: bin(x)[2:], list(map(int, input().split()))))
	s = 1
	for j in range(max(len(p), len(q), len(r))):
		i = j + 1
		if j < len(p):
			pc = p[0 - i]
		else:
			pc = '0'
		if j < len(q):
			qc = q[0 - i]
		else:
			qc = '0'
		if j < len(r):
			rc = r[0 - i]
		else:
			rc = '0'
		if pc == '1' and qc == '1' and (rc == '1'):
			s = s * 4
		elif pc == '1' and qc == '1' and (rc == '0'):
			s = s * 1
		elif pc == '1' and qc == '0' and (rc == '1'):
			s = s * 1
		elif pc == '0' and qc == '1' and (rc == '1'):
			s = s * 1
		elif pc == '0' and qc == '0' and (rc == '1'):
			s = s * 0
		elif pc == '0' and qc == '1' and (rc == '0'):
			s = s * 0
		elif pc == '1' and qc == '0' and (rc == '0'):
			s = s * 0
		elif pc == '0' and qc == '0' and (rc == '0'):
			s = s * 1
		if s == 0:
			break
	print(s)


for test in range(int(input())):
	(j, b, c) = [int(x) for x in input().split()]
	arr = [1, 0, 1, 4]
	bina = bin(j)[2:]
	binb = bin(b)[2:]
	binc = bin(c)[2:]
	bina = '{0}'.format(str(bina).zfill(20))
	binb = '{0}'.format(str(binb).zfill(20))
	binc = '{0}'.format(str(binc).zfill(20))
	r = 1
	for i in range(20):
		r *= arr[(int(bina[i]) + int(binb[i]) + int(binc[i])) % 4]
	print(r)


n = int(input())
for _ in range(n):
	(x, y, z) = map(int, input().split())
	arr = [1, 0, 1, 4]
	ans = 1
	for i in range(20):
		ans = ans * arr[(x & 1) + (y & 1) + (z & 1)]
		x = x >> 1
		y = y >> 1
		z = z >> 1
	print(ans)


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	ans = 1
	while p > 0 or q > 0 or r > 0:
		P = p & 1
		Q = q & 1
		R = r & 1
		f = P + Q + R
		if f == 3:
			ans *= 4
		if f == 1:
			ans = 0
			break
		p >>= 1
		q >>= 1
		r >>= 1
	print(ans)


for i in range(int(input())):
	(a, b, c) = [int(x) for x in input().split()]
	m = max(a, b, c)
	m1 = bin(m)[2:]
	p = len(m1)
	x = bin(a)[2:]
	x = '0' * (p - len(x)) + x
	y = bin(b)[2:]
	y = '0' * (p - len(y)) + y
	z = bin(c)[2:]
	z = '0' * (p - len(z)) + z
	t = 0
	th = 0
	for i in range(len(m1)):
		if int(x[i]) + int(y[i]) + int(z[i]) == 1:
			print(0)
			break
		if x[i] == '1' and y[i] == '1' and (z[i] == '1'):
			t += 1
		elif x[i] == '1' and y[i] == '1' or (y[i] == '1' and z[i] == '1') or (z[i] == '1' and x[i] == '1'):
			th += 1
	else:
		if t == 0:
			print(1)
		else:
			print(pow(4, t))


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	ans = 1
	for bit in range(20):
		bits = (a >> bit & 1) + (b >> bit & 1) + (c >> bit & 1)
		if bits == 1:
			ans = 0
		elif bits == 3:
			ans *= 4
	print(ans)


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	answer = 1
	while p > 0 or q > 0 or r > 0:
		num = (p & 1) + (q & 1) + (r & 1)
		if num == 3:
			answer *= 4
		if num == 1:
			answer = 0
			break
		p >>= 1
		q >>= 1
		r >>= 1
	print(answer)


for _ in range(int(input())):
	(p, q, r) = map(int, input().split())
	possibility_sum = 1
	for bit in range(0, 20):
		temp = (p >> bit & 1) + (q >> bit & 1) + (r >> bit & 1)
		if temp == 1:
			possibility_sum = 0
			break
		elif temp == 3:
			possibility_sum *= 4
	print(possibility_sum)


R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(p, q, r) = R()
	ans = 1
	for i in range(20):
		sum = (p >> i & 1) + (q >> i & 1) + (r >> i & 1)
		if sum == 3:
			if ans == 1:
				ans = 4
			else:
				ans *= 4
		if sum == 1:
			ans = 0
	print(ans)