OR Tuples Codechef Solution

Problem

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 \le A, B, C \lt 2^{20}0≤A,B,C<220

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

Sample 1:

3
10 12 14
0 5 5
0 0 7

4
1
0

Explanation:

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.