카드 게임

Shekhu 교수는 컴퓨터 과학의 초창기에 게임 이론 분야에서 연구하던 유명한 과학자였다. 현재 그는 서로 다른 카드 N개가 들어 있는 상자를 사용하는 게임을 연구하고 있다. 이 카드들 중 i번째 카드에는 한쪽 면에 빨간색 수가, 다른 쪽 면에 파란색 수가 적혀 있다. 두 수는 모두 양의 정수이다. 게임은 다음과 같이 진행된다.

• 플레이어는 총점 0점으로 시작한다. 게임의 목표는 가능한 한 가장 낮은 총점으로 끝내는 것이다.

• 상자에 카드가 적어도 두 장 남아 있는 동안 플레이어는 다음 행동을 반복해야 한다.

• 원하는 카드 두 장을 상자에서 꺼낸다. 한 카드에서 빨간색 수 R을, 다른 카드에서 파란색 수 B를 선택한다.

• 총점에 R ^ B의 값을 더한다. 여기서 ^는 비트 단위 XOR 연산을 나타낸다.

• 두 카드 중 하나를 상자에 돌려놓고, 다른 하나는 게임에서 제거한다.

• 상자에 카드가 단 한 장만 남으면 게임이 끝난다(따라서 더 이상 행동할 수 없다).

Shekhu 교수는 자신의 가장 뛰어난 학생인 Akki를 불러 이 게임을 하게 했다. Akki가 게임을 진행할 수 있는 모든 가능한 방법을 고려하여, 그가 얻을 수 있는 최소 총점을 구하도록 도와줄 수 있는가?

제한

1 ≤ T ≤ 100. 테스트 세트당 시간 제한: 20초. 메모리 제한: 1GB. 1 ≤ $R_{i}$ ≤ $10^{9}$. 1 ≤ $B_{i}$ ≤ $10^{9}$.

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

2 ≤ N ≤ 5.

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

2 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 세 줄로 이루어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어진다.

• 첫 줄에는 상자에 든 카드 수를 나타내는 양의 정수 N이 주어진다.

• 둘째 줄에는 N개의 양의 정수 $R_{i}$로 이루어진 목록이 주어진다. 이 중 i번째 정수는 i번째 카드의 빨간색 수를 나타낸다.

• 셋째 줄에는 N개의 양의 정수 $B_{i}$로 이루어진 목록이 주어진다. 이 중 i번째 정수는 i번째 카드의 파란색 수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 Akki가 최적으로 플레이할 때 얻을 수 있는 최소 총점이다.

예제 케이스 #1에서 Akki가 할 수 있는 행동은 주어진 카드들을 집어 드는 것뿐이며, 두 가지 선택지가 있다.

• 첫 번째 카드의 빨간색 수와 두 번째 카드의 파란색 수를 선택하여 총점에 1 ^ 3 = 2을 더할 수 있다.

• 두 번째 카드의 빨간색 수와 첫 번째 카드의 파란색 수를 선택하여 총점에 2 ^ 3 = 1을 더할 수 있다.

두 번째 선택지가 더 좋으므로 정답은 1이다.

예제 케이스 #2에서 한 가지 최적 전략은 첫 번째 카드의 빨간색 수와 두 번째 카드의 파란색 수를 선택하고, 총점에 1 ^ 2 = 3을 더한 뒤 첫 번째 카드를 상자에 돌려놓는 것이다. 그런 다음 첫 번째 카드의 빨간색 수와 세 번째 카드의 파란색 수를 선택하고, 총점에 1 ^ 3 = 2을 더한 뒤 두 카드 중 어느 것이든 상자에 돌려놓는다. 최종 총점은 5이다.