Cube IV (Small)

Vincenzo wanted to build cube IV, but his budget only covered one square maze. Every room of the maze is a square and has four doors, one on each side. A big number is written in every room.

A person moves from the room he is standing in to a neighboring room only when the number written there is exactly $1$ larger than the number in his own room. Two rooms are neighbors when they share a side with a door in it.

The maze has side length $S$. Vincenzo writes $1, 2, 3, \dots, S^2$ on the $S^2$ rooms, one number per room and no number twice, and then puts one person in every room, $S^2$ people in total. The person who moves the largest number of times wins. Find the number of the room the winner starts in and how many rooms he passes through. The room he starts in counts as one of them.

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

The first line of each test case contains the side length $S$ of the maze. The next $S$ lines contain $S$ numbers each, giving the numbers written in the rooms row by row from the top row of the maze.

For each test case, print one line of 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 starts in, and $d$ is the number of rooms he passes through.

If several people move the largest number of times, the one standing in the room with the smallest number wins.

• $1 \le T \le 100$
• $1 \le S \le 10$
• Each of the numbers from $1$ to $S^2$ is written in exactly one room.