2008 年被称为变革与过渡的一年，是一个新时代的开端：当然，我们指的是全新的 Google Code Jam 赛制。这项赛事的引入将如此多精彩的编程竞赛汇集在同一年，以至于人们开始称其为“Code Jam 之年”。

Sphinny 是一位热情的参赛者，她查看了自己的年度日历，发现已经安排了大量的编程竞赛。她在日历上将每一天标记为以下三种状态之一：

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

注意：为了简化问题，我们假设不存在资格赛的概念：你不需要参加某一场比赛来获得参加另一场比赛的资格。

由于 Sphinny 所处的世界与我们略有不同，她的日历有一些必须提到的特征：它有 $N$ 个月，每个月恰好有 $M$ 天。

下图描绘了一个有 5 个月、每月 8 天的日历，其中有 15 个蓝色日子和 5 个问号。

看着她美丽的日历，Sphinny 决定每一天在一年中最多有 4 个邻居：同一个月的前一天、同一个月的后一天、上个月的同一天以及下个月的同一天。

Sphinny 想要最大化她从这些比赛中获得的快乐值，她将比赛对快乐的影响估计为所有蓝色日子的价值总和。对于每一个蓝色日子，其价值计算如下：

• 初始价值为 4。
• 每有一个蓝色邻居，价值减少 1。

你可能会认为 Sphinny 喜欢比赛，但连续两天参赛会让她感到有些疲惫。出于审美原因，在连续两个月的同一天参赛也不是那么好。

Sphinny 现在想要规划她的一年，并决定每一个带有问号的日子应该是白色还是蓝色。她的目标仅仅是最大化快乐值。

下图展示了上述样例的一种解决方案。通过将两个问号改为蓝色，将另外三个改为白色，她可以获得 42 的快乐值。

输入格式

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

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

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

输出格式

对于每个测试用例，你应该输出一行格式如下：

Case #X: Y

其中 $X$ 是从 1 开始的用例编号，$Y$ 是最大快乐值。

数据范围

$1 \le T \le 100$。

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

$1 \le M, N \le 15$。

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

$1 \le M, N \le 50$。

样例

样例输入 1

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

样例输出 1

Case #1: 8
Case #2: 42

说明

注意，第二个样例就是我们上述图片中的例子。