P13472 [GCJ 2008 #3] No Cheating

一所当地的高中将在一个大教室里举行期末考试。然而，这所学校的一些学生总是试图在考试时偷看彼此的答题卡！ 教室可以看作是一个 $M$ 行 $N$ 列的矩形网格，每个单元格代表一个座位。 校长决定制定如下规则以防止作弊：假设一个学生可以看到他左边、右边、左上方和右上方邻座同学的答题卡。座位的安排必须保证没有任何人的答题卡会被其他学生看到。  如图所示，如果有人坐在 A、C、D 或 E，后排的男孩就能看到他们的答题卡，这样的安排并不好。然而，如果有女生坐在 B，他就无法看到她的答题卡。 教室中有些座位是坏的，不能安排学生坐在坏掉的座位上。 校长请你回答如下问题：在没有人能作弊的前提下，最多能安排多少名学生参加考试？

输入的第一行为测试用例数 $C$。接下来有 $C$ 组测试数据。每组测试数据包括两部分。 第一部分为一行，包含两个整数 $M$ 和 $N$，表示教室的行数和列数。 第二部分为恰好 $M$ 行，每行恰好 $N$ 个字符。每个字符为 '.'（表示该座位未坏）或 'x'（表示该座位已坏，小写字母 x）。

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

**数据范围** - $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 翻译