题目描述

Google Assistant 和 Android Auto 团队正在合作开发一款可以通过语音命令驾驶的新型原型车。早期原型通过连接汽车模拟器的手机工作。不幸的是，一位早期测试者将手机掉进了马桶，导致麦克风损坏，使得新功能更难使用。由于他们不想错过这个机会，因此希望你能帮助他们继续使用。

早期原型在一个简单的 $\mathbf{R}$ 行 $\mathbf{C}$ 列的网格上移动，仅能理解 4 个非常简单的语音命令：north（北）、south（南）、east（东）和 west（西）。每个命令会使汽车尝试向对应方向移动一格。但由于麦克风问题，系统可能会混淆 north 和 south，以及 east 和 west。这意味着 north 命令可能使汽车向北或向南移动，south 命令可能使汽车向南或向北移动，类似地，east 和 west 命令也可能使汽车向东或向西移动。在所有情况下，两种移动选项的概率均为 $(1 / 2)$。

测试者设置了一个驾驶网格，每个单元格可以是墙壁、危险区域或空地。如果命令会使汽车移动到墙壁或网格外，则汽车不会移动。如果命令会使汽车移动到危险区域，则汽车无法执行更多命令。

测试者将一些空单元格标记为有趣的起点，另一些标记为有趣的终点。如果一个有趣的起点和有趣的终点组成的配对满足：存在一种通过语音命令驾驶汽车从起点出发的策略，使得汽车以至少 $1-10^{-10^{100}}$ 的概率到达终点，则该配对是可驾驶的。策略可以根据之前命令的结果选择发出哪个命令以及何时停止。注意，如果汽车移动到危险区域，它将停止移动，因此无法到达终点。测试者希望你帮助找出所有可驾驶的配对。

输入格式

输入的第一行给出测试用例的数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例。每个测试用例的第一行包含两个整数 $\mathbf{R}$ 和 $\mathbf{C}$，表示网格的行数和列数。接下来是 $\mathbf{R}$ 行，每行包含一个长度为 $\mathbf{C}$ 的字符串。第 $i$ 行的第 $j$ 个字符 $\mathbf{G}_{\mathbf{i}, \mathbf{j}}$ 表示网格的第 $i$ 行第 $j$ 列，具体如下：

• 句点 (.) 表示不感兴趣的空单元格。
• 井号 (#) 表示包含墙壁的单元格。
• 星号 (*) 表示包含危险区域的单元格。
• 小写英文字母 (a 到 z) 表示作为有趣起点的空单元格。
• 大写英文字母 (A 到 Z) 表示作为有趣终点的空单元格。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 NONE（如果没有可驾驶的配对）。否则，$y$ 必须是由空格分隔的一系列 2 字符字符串，表示所有可驾驶的配对，起点字母在前，终点字母在后，按字母顺序排列。

输入输出样例 #1

输入 #1

4
1 2
aZ
4 4
a..c
**.*
.Y.#
bX#Z
2 2
a*
*Z
2 7
a*bcd*.
...*F#.

输出 #1

Case #1: aZ
Case #2: aY bX bY cY
Case #3: NONE
Case #4: dF

说明/提示

样例解释

在样例 #1 中，简单地重复 west 命令直到到达终点是一种可行的策略。每次有 $1 / 2$ 的概率到达终点，$1 / 2$ 的概率停留在原地。因此，在 $10^{101}$ 步或更少步内未到达终点的概率为 $2^{-10^{101}}<10^{-10^{100}}$。

在样例 #2 中，类似于样例 #1 的策略可以用于将汽车从顶行（1）的任何位置以任意高的概率移动到其他位置，类似地也适用于从顶部数第三行（2）的所有非墙壁位置。类似地，但使用 south 命令，汽车可以在从左数第三列（3）的非墙壁位置之间移动。

从 a 和 c 出发，可以使用（1）到达从左数第三列，然后使用（3）到达 $\mathrm{Y}$ 旁边，再使用（2）到达 $\mathrm{Y}$，因此 $\mathrm{aY}$ 和 $\mathrm{cY}$ 是可驾驶的。然而，从第三行安全使用 north 或 south 命令只能在第三列进行，否则汽车可能会进入危险区域。因此，无法将汽车从第三行安全移动到第四行，因此 $\mathrm{aX}$ 和 $\mathrm{cX}$ 不可驾驶。

从 $\mathrm{b}$ 出发，可以使用类似策略到达 $\mathrm{X}$，然后从 $\mathrm{X}$ 出发，通过重复使用 north 或 south 命令（并在到达 $\mathrm{Y}$ 时停止，避免进入上方的危险区域）到达 $\mathrm{Y}$。

最后，终点 $\mathrm{Z}$ 完全孤立，因此无法成为可驾驶配对的一部分。

在样例 #3 中，从有趣起点到有趣终点的每条路径都经过危险区域，因此该配对不可驾驶。

在样例 #4 中，只有有趣起点 $\mathrm{d}$ 存在可行的策略到达终点 $\mathrm{F}$。

限制

• $1 \leq \mathbf{T} \leq 100$。
• 对于所有 $i, j$，$\mathbf{G}_{\mathbf{i}, \mathbf{j}}$ 是句点 (.)、井号 (#)、星号 (*) 或小写或大写英文字母。
• 集合 $\left\{\mathbf{G}_{\mathbf{i}, \mathbf{j}}\right.$ 对于所有 $\left.i, j\right\}$ 至少包含 1 个小写和 1 个大写英文字母。
• 每个小写和大写字母在所有 $\mathbf{G}_{\mathbf{i}, \mathbf{j}}$ 中最多出现一次。

测试集 1（5 分，可见评测结果）

• $1 \leq \mathbf{R} \leq 20$。
• $1 \leq \mathbf{C} \leq 20$。

测试集 2（17 分，隐藏评测结果）

• $1 \leq \mathbf{R} \leq 100$。
• $1 \leq \mathbf{C} \leq 100$。