Go To Considered Helpful

Marlin은 아들을 잃고 그를 찾아다니는 물고기다. 다행히 그는 형제인 Wally, Seymour와 함께 헤엄치던 거북이 Cynthia를 만난다. Cynthia는 Marlin이 어디로 가야 하는지 정확히 알고 있고, 아주 정밀하게 길을 알려 줄 수 있다. Marlin은 영리해서 지시를 완벽하게 따르지만, 긴 지시 목록을 기억하기는 어렵다. Cynthia는 지시 목록을 짧게 만들어야 한다.

Marlin은 $R$행 $C$열 행렬에 산다. 일부 칸은 위험해서 들어갈 수 없다. Marlin과 아들은 서로 다른 위험하지 않은 칸에 있다. 아들은 다른 칸으로 움직이지 않는다. Cynthia는 한 줄에 하나씩 적힌 지시들의 목록, 즉 프로그램으로 길을 알려 준다. 지시는 다음 다섯 가지 중 하나다.

• N: 한 칸 북쪽(위)으로 이동
• S: 한 칸 남쪽(아래)으로 이동
• W: 한 칸 서쪽(왼쪽)으로 이동
• E: 한 칸 동쪽(오른쪽)으로 이동
• G(i): 지시 목록의 $i$번째 줄로 점프 (1부터 센다)

처음 네 가지 지시 중 하나를 실행하면, 다음 줄이 있을 경우 Marlin은 다음 줄로 넘어간다. 다음 줄이 없으면 Marlin은 그 자리에 영원히 멈춘다.

예를 들어 Marlin이 다음 프로그램을 따른다고 하자.

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

그러면 Marlin은 북쪽으로 이동하고(1행), 동쪽으로 이동하고(2행), 움직이지 않고 6행으로 점프하고(3행), 서쪽으로 이동하고(6행), 4행으로 점프하고(7행), 남쪽으로 이동하고(4행), 1행으로 점프하고(5행), 북쪽으로 이동하는(1행) 식으로 움직인다.

Marlin과 아들이 같은 칸에 있게 되면 둘은 다시 만나고, Marlin은 더 이상 지시를 따르지 않는다. Marlin이 위험한 칸에 들어가거나 행렬 밖으로 나가지 않으면서 아들과 같은 칸에 도달하게 하는 프로그램의 최소 줄 수를 구하라. 모든 G 지시는 실제로 존재하는 줄로 점프해야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 행의 수와 열의 수 $R$, $C$가 적힌 줄로 시작한다. 이어서 각각 $C$개의 문자로 이루어진 줄이 $R$개 주어진다. $i$번째 줄의 $j$번째 문자 $A_{ij}$는 위험한 칸이면 #, Marlin이 있는 칸이면 대문자 M, 아들이 있는 칸이면 대문자 N, 비어 있는 위험하지 않은 칸이면 .이다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 시작)다. 위 조건을 만족하며 Marlin을 아들에게 데려다주는 프로그램이 없으면 $y$는 IMPOSSIBLE이다. 그렇지 않으면 $y$는 그러한 프로그램의 최소 지시 수다.

• $1 \le T \le 100$.
• 모든 $A_{ij}$는 #, ., 대문자 M, 대문자 N 중 하나다.
• $A_{ij} = M$인 $(i, j)$ 쌍은 정확히 하나다.
• $A_{ij} = N$인 $(i, j)$ 쌍은 정확히 하나다.

일부 예제 케이스의 가장 짧은 프로그램은 다음과 같다.

예제 케이스 #1 (두 프로그램 중 어느 것이든 된다):

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

또는

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

예제 케이스 #2:

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

예제 케이스 #3:

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

예제 케이스 #4:

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

프로그램은 줄 수가 가장 적어야 하지만, Marlin이 움직이는 횟수까지 최소일 필요는 없다.