Marlin 是一条丢失了儿子的鱼，正在寻找他。幸运的是，他遇到了海龟 Cynthia，她正和她的兄弟 Wally 和 Seymour 一起游泳。Cynthia 确切地知道 Marlin 需要去哪里，并且在指路时非常精确。虽然 Marlin 很聪明，能够完美地遵循指令，但要记住一长串的指令可能会有困难。Cynthia 需要找到一种方法来缩短指令列表。

Marlin 生活在一个 $R$ 行 $C$ 列的矩阵中。矩阵中的某些单元格是危险的，不能进入。Marlin 和他的儿子目前位于不同的非危险单元格中。Marlin 的儿子从不移动到其他单元格。Cynthia 决定以程序的形式给 Marlin 指路，程序由一系列指令组成，每行一条。每条指令属于以下 5 种类型之一：

• N：向北（上）移动一个单元格，
• S：向南（下）移动一个单元格，
• W：向西（左）移动一个单元格，
• E：向东（右）移动一个单元格，以及
• G(i)：跳转到指令列表的第 $i$ 行（从 1 开始计数）。

在执行前 4 种指令中的任意一条后，如果列表中有下一行，Marlin 会跳转到下一行。如果没有下一行，Marlin 就会永远停在原地。

例如，如果 Marlin 遵循以下程序：

1: N
2: E
3: G(6)
4: S
5: G(1)
6: W
7: G(4)

他会先向北移动（第 1 行），然后向东移动（第 2 行），然后跳转到第 6 行而不进行物理移动（第 3 行），然后向西移动（第 6 行），然后跳转到第 4 行（第 7 行），然后向南移动（第 4 行），然后跳转到第 1 行（第 5 行），然后向北移动（第 1 行），依此类推。

如果 Marlin 和他的儿子在任何时候处于同一个单元格，他们就会团聚，Marlin 将不再遵循任何指令。海龟 Cynthia 想要找出能让 Marlin 到达他儿子所在单元格的程序的最少行数，且要求 Marlin 在过程中永远不会进入危险单元格或移出矩阵边界。所有的 G 指令必须跳转到程序中已有的行。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含 $R$ 和 $C$，即矩阵的行数和列数。接下来是 $R$ 行，每行包含一个长度为 $C$ 的字符串。这些行中第 $i$ 行的第 $j$ 个字符 $A_{ij}$ 表示矩阵中第 $i$ 行第 $j$ 列的单元格。字符 # 表示该单元格是危险的，大写字母 M 表示 Marlin 当前所在的单元格，大写字母 N 表示 Marlin 的儿子所在的单元格，. 表示一个未被占用的非危险单元格。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），如果不存在能让 Marlin 在上述条件下到达他儿子所在单元格的程序，则 $y$ 为 IMPOSSIBLE，否则 $y$ 为此类程序中最少的指令行数。

数据范围

内存限制：1GB。 $1 \le T \le 100$。 $A_{ij}$ 为 #, ., M 或 N 中的一种。 对于每个测试用例，恰好有一个单元格为 M。 对于每个测试用例，恰好有一个单元格为 N。

测试集 1（可见） 时间限制：30 秒。 $1 \le R \le 10$。 $1 \le C \le 10$。

测试集 2（隐藏） 时间限制：120 秒。 对于最多 10 个测试用例： $1 \le R \le 100$。 $1 \le C \le 100$。 对于其余测试用例： $1 \le R \le 50$。 $1 \le C \le 50$。

样例

样例输入 1

5
2 5
N...#
....M
2 5
N#...
...#M
5 5
N..##
#.###
#...#
##.##
##..M
5 5
..N##
#.###
#...#
##.##
##..M
3 3
#M#
###
#N#

样例输出 1

Case #1: 4
Case #2: 7
Case #3: 5
Case #4: 6
Case #5: IMPOSSIBLE

说明

注意，即使程序必须包含尽可能少的行数，也不要求最小化 Marlin 移动的次数。