Cube IV (Large)

Vincenzo wanted to build Cube IV, but the budget only covered one square maze. The maze is an $S \times S$ grid of rooms, so it holds $S^2$ rooms in total. Every room is a square with one door on each of its four sides, so it connects to the rooms above, below, to the left, and to the right of it.

Vincenzo wrote a number on each room, using every number from $1$ to $S^2$ exactly once. He then put one person in every room, $S^2$ people in all. A person may move only into a neighbouring room whose number is exactly $1$ larger than the number of the room they stand in. When no such neighbour exists, that person stops.

The person who moves the most times wins. Report the number of the room the winner started in and how many rooms that person stays in, counting the starting room.

The first line contains the number of test cases, $T$.

Each test case starts with $S$, the number of rooms along one side of the maze. Then come the $S^2$ room numbers in grid order: the top row first, and within each row from left to right. The numbers are separated by whitespace, and the number of values on a line is not fixed.

For each test case, print one line in the form Case #x: r d, where $x$ is the test case number starting from $1$, $r$ is the number of the room the winner started in, and $d$ is how many rooms that person stays in.

If several people stay in the same largest number of rooms, the one who started in the smallest numbered room wins.

• $1 \le T \le 100$
• $1 \le S \le 1\,000$
• The sum of $S^2$ over all test cases is at most $10^6$.
• Within one maze, every number from $1$ to $S^2$ appears exactly once.