큐브 IV

Vincenzo는 큐브 IV를 만들기로 했지만, 정사각형 미로를 만들 예산밖에 없다. 이 미로는 완전 미로이며, 모든 방은 정사각형 형태이고 문이 4개 있다(방의 각 변마다 1개). 방에는 큰 수가 적혀 있다. 다음 방의 수가 현재 방의 수보다 1만큼 클 때만 한 방에서 다른 방으로 이동할 수 있다. 이제 Vincenzo는 모든 방에 서로 다른 수를 할당하고(1, 2, 3, .... $S^{2}$), 미로의 한 변의 길이가 S일 때 $S^{2}$명의 사람을 각 방에 1명씩 배치한다. 가장 많이 이동할 수 있는 사람이 승리한다. 누가 승자가 될지와 그 사람이 이동할 수 있는 방의 수를 구한다.

제한

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

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

1 ≤ S ≤ 10

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

1 ≤ S ≤ $10^{3}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정사각형 미로의 한 변의 길이인 S로 시작한다. 그다음 방에 할당된 수를 미로 형태로 나타내는 $S^{2}$개의 수가 주어진다.

1 2 9 
5 3 8 
4 6 7

각 테스트 케이스마다 "Case #x: r d"을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, r은 승자의 방 번호이며, d는 그 사람이 이동할 수 있었던 방의 수이다. 이러한 사람이 여러 명이면 가장 작은 번호의 방에 있는 사람이 승리한다.