题目描述

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$ 是他能够移动到的房间数量。如果有多人并列最优，则房间号码最小的人获胜。

2
2
3 4
1 2
3
1 2 9
5 3 8
4 6 7 

Case #1: 1 2
Case #2: 6 4

提示

限制

$1 \le T \le 100$.

小数据集（测试集 1 - 可见）

$1 \le S \le 10$

大数据集（测试集 2 - 隐藏）

$1 \le S \le 10^3$.

翻译由 DeepSeek V4 Pro 完成