큐브 4 (라지)

빈센초는 큐브 4편을 만들려고 했지만 예산이 모자라서 정사각형 미로 하나만 지었다. 미로는 한 변에 방이 $S$개씩 놓인 $S \times S$ 격자이고, 방은 모두 $S^2$개다. 방은 하나하나가 정사각형이고 네 변마다 문이 하나씩 달려 있어서 위, 아래, 왼쪽, 오른쪽으로 맞닿은 방과 이어진다.

빈센초는 방마다 $1$부터 $S^2$까지의 번호를 겹치지 않게 하나씩 크게 써 붙였다. 그다음 방마다 한 명씩, 모두 $S^2$명을 미로에 넣었다. 사람은 지금 있는 방의 번호보다 정확히 $1$ 큰 번호가 적힌 이웃 방으로만 옮겨 갈 수 있다. 그런 이웃 방이 없으면 그 자리에서 멈춘다.

가장 여러 번 옮겨 간 사람이 우승한다. 우승자가 처음에 있던 방의 번호와 그 사람이 머문 방의 개수를 구하여라. 방의 개수는 출발한 방까지 포함해서 센다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스는 미로 한 변의 방 개수 $S$로 시작한다. 그 뒤에 방에 붙은 번호 $S^2$개가 격자 순서대로, 즉 맨 위 행부터 한 행씩, 각 행 안에서는 왼쪽에서 오른쪽 순서로 주어진다. 수는 공백이나 줄바꿈으로 구분되고, 한 줄에 몇 개가 들어 있는지는 정해져 있지 않다.

각 테스트 케이스마다 Case #x: r d 형식으로 한 줄씩 출력한다. $x$는 $1$부터 시작하는 테스트 케이스 번호, $r$은 우승자가 출발한 방의 번호, $d$는 그 사람이 머문 방의 개수다.

머문 방의 개수가 가장 큰 사람이 여럿이면 출발한 방의 번호가 가장 작은 사람이 우승한다.

• $1 \le T \le 100$
• $1 \le S \le 1\,000$
• 모든 테스트 케이스의 $S^2$을 합한 값은 $10^6$ 이하다.
• 한 미로 안에서 $1$부터 $S^2$까지의 번호가 정확히 한 번씩 나온다.