题目描述

填字游戏是一个由黑色单元格和字母 A-Z 组成的矩形网格，如下图所示。

:::align{center} :::

填字游戏中的单词定义为最长的垂直或水平字符段。在下方的填字游戏中，DO 和 ON 是单词的例子。

:::align{center} :::

一个回文填字游戏是指其中每个单词都是回文。记 $R_{i,j}$ 为第 $i$ 行第 $j$ 列的字符，$i$ 和 $j$ 均从 $1$ 开始编号。左上角为 $R_{1,1}$。在下面的回文填字游戏示例中，位于 $R_{3,2}$ 的 B 既属于从 $R_{3,1}$ 开始的水平单词，也属于结束于 $R_{4,2}$ 的垂直单词，且这两个单词都是回文。

:::align{center} :::

你被赠予了一个有 $N$ 行 $M$ 列的回文填字游戏。你完成了填字游戏，扔掉了线索，准备把它挂在墙上。然而，你不小心擦掉了一些字母！你想尽可能地恢复填字游戏，但你已经没有线索了。仅利用填字游戏是回文的这一知识，恢复给定填字游戏中尽可能多的缺失字符。

缺失的字母在下图中表示为空的白色单元格。左侧的填字游戏是你得到的，右侧的填字游戏是你在恢复了尽可能多的字母后的结果。剩余的单元格无法填充，因为我们没有足够的信息来恢复它们。

:::align{center} :::

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $M$，分别表示填字游戏的行数和列数。

接下来的 $N$ 行表示网格的 $N$ 行。第 $i$ 行由 $M$ 个字符组成，表示 $R_{i,1}, R_{i,2}, \dots, R_{i,M}$。每个字符是以下之一：

• 大写字母（A-Z）
• 句点（.）表示缺失的字母（在示例填字游戏中为空的白色单元格）
• 井号（#）表示黑色单元格

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是被填充的空白色单元格的数量。然后，输出 $N$ 行，表示最终的网格，其中缺失的字符（.）在可能的情况下被替换为大写字母（A-Z）。

2
2 2
A.
.#
4 6
A...#.
B##...
B.###.
A...#.

Case #1: 2
AA
A#
Case #2: 8
A..A#.
B##A.A
BB###A
ABBA#.

提示

在样例 #2 中，我们可以填充 $8$ 个空白。填充缺失字母的方式如下：

• 第 $1$ 行第 $4$ 列：由第 $1$ 行第 $1$ 列的字符可知为 A。
• 第 $2$ 行第 $4$ 列 = 第 $1$ 行第 $4$ 列的 A。
• 第 $2$ 行第 $6$ 列 = 第 $2$ 行第 $4$ 列的 A。
• 第 $3$ 行第 $6$ 列 = 第 $2$ 行第 $6$ 列的 A。
• 第 $3$ 行第 $2$ 列 = 第 $3$ 行第 $1$ 列的 B。
• 第 $4$ 行第 $2$ 列 = 第 $3$ 行第 $2$ 列的 B。
• 第 $4$ 行第 $3$ 列 = 第 $4$ 行第 $2$ 列的 B。
• 第 $4$ 行第 $4$ 列 = 第 $4$ 行第 $1$ 列的 A。

限制条件

$1 \le T \le 100$。

至少存在一种填充方式，使得给定的输入网格成为回文填字游戏。

网格中的所有字符均属于集合 $\{\texttt{A-Z}, \#, .\}$。

测试集 1

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

测试集 2

最多 $10$ 个测试用例满足：

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

其余测试用例满足：

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

翻译由 DeepSeek V4 Pro 完成