你正在为一些孩子筹办派对，并准备了一个 $R$ 行 $C$ 列的网格状蛋糕。你的助手已经开始装饰蛋糕，在蛋糕的每一个格子上写下了每个孩子的名字首字母。每个格子最多包含一个首字母，且由于没有两个孩子共用同一个首字母，因此每个首字母在蛋糕上最多出现一次。

每个孩子都想要一块包含他们名字首字母且不包含其他孩子首字母的矩形（与网格对齐）蛋糕。你能找到一种方法将蛋糕上的每一个空白格子分配给一个孩子，从而实现这个目标吗？题目保证这总是可能的。不需要将蛋糕平均分配给孩子们，他们中的一个或多个甚至可能只得到一块 $1 \times 1$ 的蛋糕；这将是关于不公平的一堂宝贵的人生课。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $R$ 和 $C$。接下来的 $R$ 行，每行包含 $C$ 个字符，代表蛋糕。每个字符要么是一个大写英文字母（表示你的助手已经在该格子中填入了该字母），要么是 ?（表示该格子是空白的）。

输出格式

对于每个测试用例，输出一行 Case #x:，其中 $x$ 是测试用例编号。然后输出 $R$ 行，每行 $C$ 个字符。你的输出网格必须与输入网格相同，但所有的 ? 都必须替换为大写英文字母，表示该格子属于拥有该首字母的孩子。你不能添加输入中原本没有出现的字母。在你的网格中，对于每个字母，由所有包含该字母的格子组成的区域必须是一个单一的、与网格对齐的矩形。

如果存在多种可能的答案，你可以输出其中任意一种。

数据范围

时间限制：每个测试集 20 秒。 内存限制：1 GB。 $1 \le T \le 100$。 输入网格中至少包含一个字母。 没有字母在输入网格中出现超过一次。 保证每个测试用例至少存在一个答案。

小型数据集（测试集 1 - 可见）： $1 \le R \le 12$ $1 \le C \le 12$ $R \times C \le 12$

大型数据集（测试集 2 - 隐藏）： $1 \le R \le 25$ $1 \le C \le 25$

样例

样例输入 1

3
3 3
G??
?C?
??J
3 4
CODE
????
?JAM
2 2
CA
KE

样例输出 1

Case #1:
GGJ
CCJ
CCJ
Case #2:
CODE
COAE
JJAM
Case #3:
CA
KE

说明

样例输出展示了针对样例测试用例的一组答案。其他答案也可能是可能的。