P16490 [GKS 2014 #D] Cube IV

Vincenzo 决定制作“立方体 IV”，但预算只够做一个正方形迷宫。这是一个完美的迷宫，每个房间都是正方形，并且有 $4$ 扇门（每边一扇）。房间内写有一个很大的数字。一个人只有当相邻房间的数字恰好比当前房间的数字大 $1$ 时，才能从当前房间移动到那个房间。现在，Vincenzo 为所有房间分别分配了唯一的数字（$1$，$2$，$3$，……，$S^2$），并在迷宫中放置了 $S^2$ 个人，每个房间一人，其中 $S$ 是迷宫的边长。移动次数最多的人将获胜。请找出谁将获胜，以及他能够移动到的房间数量。

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例首先给出整数 $S$，表示正方形迷宫的边长。随后按照迷宫布局给出 $S^2$ 个数字，依次为分配给各个房间的号码。 例如： $1$ $2$ $9$ $5$ $3$ $8$ $4$ $6$ $7$

对于每个测试用例，输出一行形如 "Case #x: r d" 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$r$ 是获胜者所在房间的号码，$d$ 是他能够移动到的房间数量。如果有多人并列最优，则房间号码最小的人获胜。

### 限制 $1 \le T \le 100$. **小数据集（测试集 1 - 可见）** $1 \le S \le 10$ **大数据集（测试集 2 - 隐藏）** $1 \le S \le 10^3$. 翻译由 DeepSeek V4 Pro 完成