P12963 [GCJ Farewell Round #4] Hey Google, Drive!

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