Description

2008 年将被称为变革与转折之年，是新时代的开始：我们当然说的是全新的 Google Code Jam 赛制。今年举办了如此多精彩的编程竞赛，以至于人们开始称其为“Code Jam 之年”。

热情的参赛者 Sphinny 正在查看她这一年的日历，发现有大量编程比赛已经安排好。她在日历上的每一天都做了如下三种标记之一：

• 白色：这一天她不会参加比赛。要么没有比赛安排，要么她有更重要的事情要做（生活中肯定还有其他美好的事物！）。
• 蓝色：这一天她一定会参加比赛。
• 问号：这一天有比赛安排，但她还没有决定是否参加。

注意：为简化问题，我们假设没有资格赛的概念：你不需要参加某场比赛才能有资格参加另一场。

在 Sphinny 所处的世界中，她的日历有一些我们必须说明的特点：它有 $N$ 个月，每个月恰好有 $M$ 天。

下图展示了一个有 5 个月、每月 8 天、15 个蓝色日和 5 个问号的日历。

Sphinny 看着她漂亮的日历，决定每一天最多有 4 个邻居：同一个月的前一天、同一个月的后一天、同一天的上一个月、同一天的下一个月。

Sphinny 希望通过这些比赛最大化她的幸福感，她估算幸福值的方法是对所有蓝色日的数值求和。对于每一个蓝色日，其数值计算如下：

• 初始值为 4。
• 每有一个蓝色邻居，该日的数值减少 1。

你可能会觉得 Sphinny 很喜欢比赛，但连续两天参赛会让她有点疲惫。出于美学原因，在连续两个月的同一天参赛也不是很理想。

Sphinny 现在想要规划她的全年日程，决定每一个问号日到底是白色还是蓝色。她的目标很简单：让幸福值最大化。

下图展示了上述例子的一个解法。通过将两个问号改为蓝色日，将另外三个改为白色日，她可以获得 42 的幸福值。

Input Format

输入文件的第一行包含用例数 $T$。接下来是 $T$ 个用例，每个用例如下格式。

第一行为 "$N$ $M$"，其中 $N$ 和 $M$ 分别表示月份数和每月天数。

接下来的 $N$ 行，每行包含一个长度为 $M$ 的字符串。第 $i$ 行第 $j$ 个字符属于 {'#', '.', '?'}，分别表示第 $i$ 个月第 $j$ 天的状态。'#' 表示蓝色日，'.' 表示白色日，'?' 表示问号日。

Output Format

对于每个输入用例，输出一行，格式如下：

Case #X: Y

其中 $X$ 是用例编号（从 1 开始），$Y$ 是最大幸福值。

2
3 3
.?.
.?.
.#.
5 8
.#...##.
.##..?..
.###.#.#
??#..?..
###?#...

Case #1: 8
Case #2: 42

Hint

样例说明

请注意，第二个样例就是上面图片中的例子。

数据范围

• $1 \leqslant T \leqslant 100$。

小数据集（7 分，测试点 1 - 可见）

• 时间限制：30 3 秒。
• $1 \leqslant M, N \leqslant 15$。

大数据集（23 分，测试点 2 - 隐藏）

• 时间限制：120 12 秒。
• $1 \leqslant M, N \leqslant 50$。

由 ChatGPT 4.1 翻译