Description

一所当地的高中将在一个大教室里举行期末考试。然而，这所学校的一些学生总是试图在考试时偷看彼此的答题卡！

教室可以看作是一个 $M$ 行 $N$ 列的矩形网格，每个单元格代表一个座位。

校长决定制定如下规则以防止作弊：假设一个学生可以看到他左边、右边、左上方和右上方邻座同学的答题卡。座位的安排必须保证没有任何人的答题卡会被其他学生看到。

如图所示，如果有人坐在 A、C、D 或 E，后排的男孩就能看到他们的答题卡，这样的安排并不好。然而，如果有女生坐在 B，他就无法看到她的答题卡。

教室中有些座位是坏的，不能安排学生坐在坏掉的座位上。

校长请你回答如下问题：在没有人能作弊的前提下，最多能安排多少名学生参加考试？

Input Format

输入的第一行为测试用例数 $C$。接下来有 $C$ 组测试数据。每组测试数据包括两部分。

第一部分为一行，包含两个整数 $M$ 和 $N$，表示教室的行数和列数。

第二部分为恰好 $M$ 行，每行恰好 $N$ 个字符。每个字符为 '.'（表示该座位未坏）或 'x'（表示该座位已坏，小写字母 x）。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 表示测试用例编号（从 1 开始），$Y$ 表示在教室中最多能安排的学生人数。

4
2 3
...
...
2 3
x.x
xxx
2 3
x.x
x.x
10 10
....x.....
..........
..........
..x.......
..........
x...x.x...
.........x
...x......
........x.
.x...x....

Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 46

Hint

数据范围

• $C=20$

小数据范围（10 分，测试点 1 - 可见）

• $1 \leqslant M \leqslant 10$
• $1 \leqslant N \leqslant 10$

大数据范围（20 分，测试点 2 - 隐藏）

• $1 \leqslant M \leqslant 80$
• $1 \leqslant N \leqslant 80$

由 ChatGPT 4.1 翻译