Go To Considered Helpful

Marlin is a fish who lost his son and is trying to find him. Fortunately, he runs into Cynthia, a turtle, as she swims around with her brothers, Wally and Seymour. Cynthia knows exactly where Marlin needs to go and can give very precise directions. Marlin is smart and follows them perfectly, but keeping track of a long list of directions is hard. Cynthia needs to make the list short.

Marlin lives in a matrix of $R$ rows and $C$ columns. Some cells are dangerous and cannot be entered. Marlin and his son are in different non-dangerous cells. The son never moves to a different cell. Cynthia gives directions as a program: a list of instructions, one per line. Each instruction is one of five types:

• N: move one cell north (up)
• S: move one cell south (down)
• W: move one cell west (left)
• E: move one cell east (right)
• G(i): jump to line $i$ of the instruction list (counting from 1)

After one of the first four instructions, Marlin moves to the next line if there is one. If there is no next line, Marlin stands still forever.

For example, if Marlin follows this program:

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

he moves north (line 1), then east (line 2), then jumps to line 6 without moving (line 3), moves west (line 6), jumps to line 4 (line 7), moves south (line 4), jumps to line 1 (line 5), moves north (line 1), and so on.

If Marlin and his son are ever in the same cell, they are reunited and Marlin stops following instructions. Find the smallest number of lines in a program that gets Marlin to the same cell as his son, without Marlin ever entering a dangerous cell or leaving the matrix. Every G instruction must jump to an existing line.

The first line contains the number of test cases $T$. Each test case starts with a line containing $R$ and $C$. Then $R$ lines follow, each a string of $C$ characters. The $j$-th character of the $i$-th line, $A_{ij}$, is # if the cell is dangerous, an uppercase M if Marlin is in that cell, an uppercase N if Marlin's son is in that cell, and . if the cell is empty and non-dangerous.

For each test case, output one line in the form Case #x: y, where $x$ is the test case number (starting from 1). $y$ is IMPOSSIBLE if no program brings Marlin to his son under the conditions above. Otherwise, $y$ is the smallest number of instructions in such a program.

• $1 \le T \le 100$.
• Each $A_{ij}$ is #, ., uppercase M, or uppercase N.
• Exactly one pair $(i, j)$ has $A_{ij} = M$.
• Exactly one pair $(i, j)$ has $A_{ij} = N$.

Below are shortest programs for some of the sample cases.

Sample Case #1 (either program works):

1: W
2: N
3: S
4: G(1)

or

1: W
2: N
3: W
4: G(3)

Sample Case #2:

1: N
2: W
3: W
4: S
5: W
6: W
7: N

Sample Case #3:

1: W
2: W
3: N
4: N
5: G(2)

Sample Case #4:

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

The program must have the fewest possible lines, but it does not need to minimize the number of moves Marlin makes.