题目描述

扫雷是一款在 20 世纪 80 年代流行起来的电脑游戏，至今仍被某些版本的 Microsoft Windows 操作系统收录。本题与扫雷有相似的思路，但并不假设你玩过扫雷。

在本题中，你正在一个由相同格子组成的网格上进行游戏。每个格子的内容最初是隐藏的。网格中有 $M$ 枚地雷，分别隐藏在 $M$ 个不同的格子中。其他格子均不含雷。你可以点击任意格子将其翻开。如果翻开的格子含有地雷，游戏立即结束，你输了。否则，翻开的格子会显示一个介于 $0$ 到 $8$ 之间（含两端）的数字，该数字表示其周围相邻格子中含有地雷的个数。如果两个格子共享一个角或一条边，则称它们相邻。此外，如果翻开的格子显示为 $0$，那么该格子所有相邻的格子也会被自动翻开，这一过程会递归进行。当所有不含地雷的格子都被翻开后，游戏结束，你获胜。

例如，一个初始的棋盘配置可能如下所示（* 代表地雷，c 是第一个被点击的格子）：

*..*...**.
....*.....
..c..*....
........*.
..........

被点击的格子周围没有地雷，因此它翻开后显示 $0$，并且它周围的 $8$ 个相邻格子也会被翻开。这一过程持续进行，最终得到如下棋盘：

*..*...**.
1112*.....
00012*....
00001111*.
00000001..

此时，仍有一些不含雷的格子未被翻开（用 . 字符表示），因此玩家必须再次点击以继续游戏。

你希望尽快赢得游戏，因此想要求出赢得游戏所需的最少点击次数。给定棋盘的大小（$N \times N$），请输出这一最少点击次数。

输入格式

第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。随后 $N$ 行，每行是一个长度为 $N$ 的字符串，由 * 和 . 组成，表示扫雷游戏的初始棋盘。

输出格式

对于每个测试用例，输出一行形如 Case #x: y 的内容，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是赢得游戏所需的最少点击次数。

2
3
..*
..*
**.
5
..*..
..*..
.*..*
.*...
.*...

Case #1: 2
Case #2: 8

提示

限制

$1 \le T \le 100$。

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

$1 \le N \le 50$。

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

$1 \le N \le 300$。

翻译由 DeepSeek V4 Pro 完成