Description

盗贼大师 Jom Codd 能够潜入他人的梦境。由于梦境观察技术还不够先进，Codd 看到的梦境是一个由单元格组成的梦境网格，每个单元格要么是白色，要么是黑色。

给定一个初始的梦境网格，Codd 可以通过“深入”操作，将每个白色单元格替换为一个 $2\times 2$ 的白色单元格网格，每个黑色单元格替换为一个 $2\times 2$ 的黑色单元格网格；这样会生成一个面积扩大四倍的新梦境网格。他可以在此基础上继续深入，如此反复。例如，给定如下初始梦境网格：

BBB
BWB
BBB

深入一次后，得到的新梦境网格为：

BBBBBB
BBBBBB
BBWWBB
BBWWBB
BBBBBB
BBBBBB

再深入一次，得到的新梦境网格为：

BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBWWWWBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB
BBBBBBBBBBBB

以此类推。

Codd 刚刚潜入了一个梦境，并看到了它的初始梦境网格。他正执行一项极其艰难的任务，他知道自己需要多次深入。为了帮助自己导航，他正在观察初始梦境网格中的各种“模式”。一个模式由一组通过边相连（仅共享角不算相连）的单元格及其颜色组成。一个模式可以包含内部空洞（只要模式的单元格是一个连通块）；这些空洞不算作模式的一部分。如果两个模式的单元格数量和排列方式完全相同（不允许翻转或旋转），且颜色一致，则认为它们是相同的模式。

例如，在上述网格中，以下 $8$ 个单元格的模式出现在初始网格中：

BBB
B B
BBB

在深入一次后，这个模式不再出现，但在深入两次、三次及之后的每一次深入的梦境网格中，这个模式都会出现。

Codd 想要找到初始梦境网格中，能够在至少 $10^{100}$ 个更深层梦境网格中出现的最大模式。对于给定的例子，上述模式就是最大的满足条件的模式。尽管它在深入一次后没有出现，但在至少 $10^{100}$ 个更深层网格中都会出现。其他更小的模式也满足条件，但不存在 $9$ 个单元格的模式满足条件；唯一可能的 $9$ 个单元格模式只能是整个初始梦境网格，但这个模式在任何更深层网格中都不会出现，更不用说出现 $10^{100}$ 次了。

Input Format

第一行输入一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组数据第一行包含两个整数 $R$ 和 $C$，分别表示梦境网格的行数和列数。接下来的 $R$ 行，每行包含 $C$ 个字符，每个字符为 B 或 W，直接表示梦境网格。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是满足 Codd 要求的最大模式的大小。

5
3 3
BBB
BWB
BBB
2 3
BBB
WBW
1 1
W
3 3
WBW
BWB
WBW
2 4
BBWW
BBWW

Case #1: 8
Case #2: 5
Case #3: 1
Case #4: 4
Case #5: 8

Hint

样例解释

样例 1 即为题目描述中的例子。

样例 2 中，一个可能的最大模式为：

BBB
WB

另一个同样大小的模式为：

BBB
W W

样例 3 中，整个初始梦境网格就是最大的模式。

样例 4 中，注意五个 W 不能构成一个合法模式，因为它们不是连通的。然而，以下模式是一个最大模式：

WB
BW

样例 5 中，整个初始梦境网格就是最大的模式。需要注意的是，尽管这个网格恰好是从 BW 深入得到的，但这与本题无关；Codd 永远不会“向上回溯”。

数据范围

• $1 \leq T \leq 100$。

测试点 1（10 分，公开）

• $1 \leq R \leq 3$。
• $1 \leq C \leq 4$。

测试点 2（22 分，隐藏）

• $1 \leq R \leq 20$。
• $1 \leq C \leq 20$。

由 ChatGPT 4.1 翻译