로봇 록 밴드 (Large)

당신은 세계 최초의 로봇 록 밴드 Xorbitant의 매니저다. 밴드에는 자리가 네 개 있고, 자리마다 로봇 $N$대가 오디션을 본다. 한 로봇이 두 자리 이상에 지원하는 일은 없다. 로봇에는 번호가 하나씩 붙어 있고, 사람 이름이 겹치듯 서로 다른 로봇의 번호가 같을 수도 있다.

시장 조사에 따르면 로봇 관객은 밴드 구성원의 연주 실력에도, 외모에도, 타블로이드가 쓴 추문에도 관심이 없다. 관객이 확인하는 것은 하나뿐이다. 네 구성원의 번호를 모두 비트 단위 XOR 한 값이 유행하는 수 $K$와 같은지다.

이 조건을 만족하도록 자리마다 로봇을 한 대씩, 모두 네 대를 고르는 방법은 몇 가지인가? 다시 말해 각각 수 $N$개가 들어 있는 네 리스트 $A$, $B$, $C$, $D$가 주어질 때, $A$에서 $a$, $B$에서 $b$, $C$에서 $c$, $D$에서 $d$를 하나씩 골라 $a \oplus b \oplus c \oplus d = K$가 되게 하는 방법의 수를 구하라. 여기서 $\oplus$는 비트 단위 XOR이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 정수 $N$과 $K$가 공백으로 구분되어 주어진다. 이어지는 네 줄에는 각각 한 자리에 지원한 로봇의 번호 $N$개가 공백으로 구분되어 주어진다. 네 줄은 차례대로 리스트 $A$, $B$, $C$, $D$다.

제한

• $1 \le T \le 10$
• $0 \le K \le 10^9$
• 모든 로봇 번호는 $0$ 이상 $10^9$ 이하다.
• $1 \le N \le 1000$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 조건을 만족하는 밴드 구성의 수다.

예제 1의 첫 번째 테스트 케이스에서 XOR 값이 $3$이 되려면 두 번째 리스트에서 $2$를, 네 번째 리스트에서 $1$을 골라야 한다. 첫 번째와 세 번째 리스트에서는 $0$ 두 개 중 어느 쪽을 골라도 되므로 조건을 만족하는 밴드는 $2 \times 2 = 4$가지다. 네 가지 모두 $(0, 2, 0, 1)$ 형태이지만 리스트에서 고른 로봇이 다르므로 서로 다른 밴드로 센다.