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.

见题面

见题面