Google Assistant 和 Android Auto 团队正在合作开发一款可以通过语音指令驾驶的原型车。该原型车通过连接到汽车模拟器的手机进行工作。不幸的是，其中一名早期测试人员不小心将手机掉进了马桶，损坏了麦克风，使得使用这项新功能变得更加困难。由于他们不想错过这个机会，他们希望你能帮助他们继续使用它。

该原型车在一个简单的 $R$ 行 $C$ 列的网格上移动，并且只能理解 4 条非常简单的语音指令：北（north）、南（south）、东（east）和西（west）。每条指令都会使汽车尝试在相应方向上移动恰好一个单元格。然而，由于麦克风的问题，系统可能会听错，将北和南互换，或者将东和西互换。这意味着，发出“北”的指令可能会使汽车向北或向南移动；发出“南”的指令可能会使汽车向南或向北移动；同样，发出“东”或“西”的指令也可能使汽车向东或向西移动。在所有情况下，两种移动方式发生的概率相等（$1/2$）。

测试人员设置了一个驾驶网格，使得每个单元格要么包含墙壁、危险，要么是空的。如果指令会导致汽车移动到墙壁中或网格之外，它将保持原地不动。如果指令导致汽车移动到危险区域，汽车将无法执行任何后续指令。

测试人员在网格中标记了一些空单元格作为“有趣的起点”，另一些作为“有趣的终点”。如果存在一种策略，可以通过语音指令从起点驾驶汽车，并以至少 $1 - 10^{-10^{100}}$ 的概率到达终点，则称这对“有趣的起点”和“有趣的终点”是“可驾驶的”。策略可以根据之前指令的结果来选择要发出的指令以及何时停止。请注意，如果汽车移动到危险区域，它将停止移动，因此无法到达终点。测试人员希望你帮助找出所有可驾驶的对。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $R$ 和 $C$，表示网格的行数和列数。接下来 $R$ 行，每行包含一个长度为 $C$ 的字符串。这些行中第 $i$ 行的第 $j$ 个字符表示网格中第 $i$ 行第 $j$ 列的单元格，具体如下：

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

输出格式

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

数据范围

$1 \le T \le 100$。 $G_{i,j}$ 对于所有 $i, j$ 均为句点 (.)、井号 (#)、星号 (*) 或小写/大写英文字母。 对于所有 $i, j$ 的集合 $\{G_{i,j}\}$ 包含至少 1 个小写英文字母和至少 1 个大写英文字母。 每个小写和大写字母在所有 $G_{i,j}$ 中最多出现一次。

测试集 1（可见判定） $1 \le R \le 20$ $1 \le C \le 20$

测试集 2（隐藏判定） $1 \le R \le 100$ $1 \le C \le 100$

样例

样例输入 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 中，简单地重复“西”指令直到到达终点是一个可行的策略。每次都有 $1/2$ 的概率到达终点，有 $1/2$ 的概率停留在原地。因此，在 $10^{101}$ 或更少的步数内未到达终点的概率小于 $2^{-10^{101}} < 10^{-10^{100}}$。

在样例 2 中，可以使用与样例 1 类似的策略，以所需的极高概率将汽车从顶行（第 1 行）的任何位置移动到其他任何位置，对于第三行（第 3 行）的所有非墙壁位置也是如此。类似地，使用“南”指令，汽车可以在从左侧数第三列（第 3 列）的非墙壁位置之间移动。

从 a 和 c 出发，我们可以使用（1）到达从左侧数第三列，然后使用（3）到达 Y 的正旁边，再使用（2）到达 Y，使得 aY 和 cY 均可驾驶。然而，请注意，从第三行安全地使用“北”或“南”指令只能在第三列进行，否则汽车可能会进入危险区域。因此，没有安全的方法将汽车从第三行移动到第四行，使得 aX 和 cX 不可驾驶。

从 b 出发，汽车可以使用类似的策略到达 X，从 X 出发，汽车可以通过重复使用“北”或“南”指令到达 Y（并在到达 Y 时停止，永远不会冒着进入上方危险区域的风险）。

最后，终点 Z 是完全隔离的，因此它不能成为可驾驶对的一部分。

在样例 3 中，从有趣起点到有趣终点的每一条路径都经过一个危险区域，这使得该对不可驾驶。

在样例 4 中，只有有趣起点 d 有可行的策略到达终点 F。