扫雷

题目描述

扫雷是一种计算机游戏，在20世纪80年代开始流行，并且仍然包含在某些版本的 Microsoft Windows 操作系统中。

在这个问题中，你正在一个矩形网格上玩扫雷游戏。

最初网格内的所有单元格都呈未打开状态。

其中M个不同的单元格中隐藏着M个地雷。

其他单元格内不包含地雷。

你可以单击任何单元格将其打开。

如果你点击到的单元格中包含一个地雷，那么游戏就会判定失败。

如果你点击到的单元格内不含地雷，则单元格内将显示一个0到8之间的数字（包括0和8），这对应于该单元格的所有相邻单元格中包含地雷的单元格的数量。

如果两个单元格共享一个角或边，则它们是相邻单元格。

另外，如果某个单元格被打开时显示数字0，那么它的所有相邻单元格也会以递归方式自动打开。

当所有不含地雷的单元格都被打开时，游戏就会判定胜利。

例如，网格的初始状态可能如下所示（*表示地雷，而c表示第一个点击的单元格）：

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

被点击的单元格旁边没有地雷，因此当它被打开时显示数字0，并且它的8个相邻单元也被自动打开，此过程不断继续，最终状态如下：

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

此时，仍有不包含地雷的单元格（用.字符表示）未被打开，因此玩家必须继续点击未打开的单元格，使游戏继续进行。

你想尽快赢得游戏胜利并希望找到赢得游戏的最低点击次数。

给定网格的尺寸（N×N），输出能够获胜的最小点击次数。

输入描述

第一行包含整数T，表示共有T组测试数据。

每组数据第一行包含整数N，表示游戏网格的尺寸大小。

接下来N行，每行包含一个长度为N的字符串，字符串由.（无雷）和*（有雷）构成，表示游戏网格的初始状态。

输出描述

每组数据输出一个结果，每个结果占一行。

结果表示为Case #x: y，其中xx是组别编号（从1开始），y是获胜所需的最小点击次数。

数据范围

1≤T≤100,
1≤N≤300