최소 스칼라곱

두 벡터 $v_{1}$ = ($x_{1}$, $x_{2}$, ..., $x_{n}$)와 $v_{2}$ = ($y_{1}$, $y_{2}$, ..., $y_{n}$)가 주어진다. 이 벡터들의 스칼라곱은 $x_{1}$ $y_{1}$ + $x_{2}$ $y_{2}$ + ... + $x_{n}$ $y_{n}$로 계산되는 하나의 수이다.

각 벡터의 좌표를 원하는 대로 순열화할 수 있다고 하자. 새로 얻은 두 벡터의 스칼라곱이 가능한 한 가장 작아지도록 두 순열을 선택하고, 그 최소 스칼라곱을 출력한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB.

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

T = 1000 1 ≤ n ≤ 8 -1000 ≤ $x_{i}$, $y_{i}$ ≤ 1000

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

T = 10 100 ≤ n ≤ 800 -100000 ≤ $x_{i}$, $y_{i}$ ≤ 100000

입력 파일의 첫 줄에는 테스트 케이스의 수인 정수 T가 주어진다. 각 테스트 케이스에서 첫 줄에는 정수 n이 주어진다. 다음 두 줄에는 각각 n개의 정수가 주어지며, 각각 $v_{1}$와 $v_{2}$의 좌표를 나타낸다.

각 테스트 케이스마다 다음 한 줄을 출력한다.

Case #X: Y

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 주어진 두 벡터의 모든 순열 중 최소 스칼라곱이다.