로봇 록 밴드

여러분은 세계 최초의 로봇 록 밴드 Xorbitant의 매니저이다. 밴드에는 네 자리가 있으며, 각 자리에 N대의 로봇이 오디션을 본다. (어떤 로봇도 둘 이상의 자리에 오디션을 보지 않는다.) 모든 로봇에는 번호가 있으며, 두 사람의 이름이 같을 수 있는 것처럼 여러 로봇의 번호가 같을 수도 있다.

시장 조사에 따르면 로봇 관객들은 로봇 밴드 멤버들의 연주 실력이나 외모, 또는 타블로이드지가 그들에 관해 보도하는 추문에는 관심을 두지 않는다. 대신 관객들은 네 멤버의 번호를 함께 비트 단위 XOR했을 때 특정한 유행 숫자 K와 같은지 확인한다.

이 속성을 갖는 밴드가 되도록 네 로봇을 각 자리에 한 대씩 선택할 수 있는 서로 다른 방법은 몇 가지인가? 더 구체적으로, 각각 N개의 수를 포함하는 네 목록 A, B, C, D가 주어질 때, 목록 A에서 수 a 하나, 목록 B에서 수 b 하나를 선택하는 식으로 각 목록에서 하나씩 선택하여 $a^b$^$c^d$ = K가 되게 하는 방법은 몇 가지인가? (여기서 ^는 비트 단위 XOR 연산을 나타낸다.)

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 10. 0 ≤ K ≤ $10^{9}$. 0 ≤ 모든 로봇 번호 ≤ $10^{9}$.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 30초. 1 ≤ N ≤ 50.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 90초. 1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 공백으로 구분된 두 정수 N과 K가 있는 한 줄로 시작한다. 그다음 네 줄이 더 주어진다. 각 줄에는 공백으로 구분된 N개의 정수가 있으며, 밴드의 특정 자리에 오디션을 보는 로봇들의 ID 번호를 나타낸다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 조건을 만족하는 서로 다른 밴드의 수이다.

예제 케이스 #1에서 결합된 비트 단위 XOR의 결과가 3이 되려면, 두 번째 목록에서 선택한 로봇은 2이어야 하고 네 번째 목록에서 선택한 로봇은 1이어야 한다. 첫 번째 목록과 세 번째 목록에서는 각각 두 0 로봇 중 어느 쪽이든 선택할 수 있으므로, 조건을 만족하는 가능한 밴드는 2 * 2 = 4개이다. 이 밴드들이 모두 (0, 2, 0, 1) 형태이더라도 목록에서 선택한 항목이 서로 다르므로 서로 다른 밴드로 간주한다.