Robot Rock Band (Large)

You manage Xorbitant, the world's first robot rock band. The band has four positions, and $N$ robots audition for each position. No robot auditions for more than one position. Every robot carries a number, and two robots can carry the same number, the way two people can share a name.

Market research says the robot audience does not care how well the members play, how they look, or what the tabloids print about them. The audience checks one thing: whether the bitwise XOR of the four members' numbers equals the trendy number $K$.

How many different sets of four robots, one per position, give the band that property? Put another way, four lists $A$, $B$, $C$, $D$ hold $N$ numbers each. Count the ways to pick one number $a$ from $A$, one number $b$ from $B$, one number $c$ from $C$, and one number $d$ from $D$ so that $a \oplus b \oplus c \oplus d = K$, where $\oplus$ is bitwise XOR.

The first line holds the number of test cases $T$. Each test case starts with a line holding two space separated integers $N$ and $K$. Four lines follow. Each holds $N$ space separated integers, the numbers of the robots auditioning for one position. The four lines give the lists $A$, $B$, $C$, $D$ in that order.

Limits

• $1 \le T \le 10$
• $0 \le K \le 10^9$
• Every robot number is between $0$ and $10^9$.
• $1 \le N \le 1000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of bands that meet the condition.

In the first test case of example 1, the XOR has to be $3$, so the robot taken from the second list must be $2$ and the robot taken from the fourth list must be $1$. Either of the two $0$ robots works for the first and the third list, so $2 \times 2 = 4$ bands meet the condition. All four bands read $(0, 2, 0, 1)$, but they count as different because the robots picked from the lists differ.