Go To는 유용한 것으로 간주된다

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이 위험한 칸에 들어가거나 행렬의 경계 밖으로 이동하는 일이 전혀 없으면서 아들과 같은 칸에 도달하게 하는 프로그램의 최소 줄 수를 알아내고 싶다. 모든 G 명령어는 프로그램에 존재하는 줄로 점프해야 한다.

제한

메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i와 j에 대해, $A_{ij}$는 #, ., 대문자 M, 대문자 N 중 하나이다. 정확히 하나의 i와 j의 쌍에 대해 $A_{ij}$ = M이다. 정확히 하나의 i와 j의 쌍에 대해 $A_{ij}$ = N이다.

테스트 세트 1 (공개)

시간 제한: 30초. 1 ≤ R ≤ 10. 1 ≤ C ≤ 10.

테스트 세트 2 (비공개)

시간 제한: 120초.

최대 10개의 테스트 케이스에 대해: 1 ≤ R ≤ 100. 1 ≤ C ≤ 100.

나머지 테스트 케이스에 대해: 1 ≤ R ≤ 50. 1 ≤ C ≤ 50.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 행렬의 행과 열의 수인 R과 C가 포함된 한 줄로 시작한다. 그다음 각각 C개의 문자로 이루어진 문자열이 포함된 R개의 줄이 주어진다. 이 줄들 중 i번째 줄의 j번째 문자 $A_{ij}$는 행렬의 i번째 행, j번째 열에 있는 칸을 나타낸다. 해당 칸이 위험하면 문자는 #이고, Marlin이 현재 있는 칸이면 대문자 M이며, Marlin의 아들이 현재 있는 칸이면 대문자 N이고, 비어 있는 위험하지 않은 칸이면 .이다.

각 테스트 케이스마다 Case #x: y가 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 위에서 설명한 조건에 따라 Marlin을 아들에게 도달하게 할 프로그램이 없다면 IMPOSSIBLE이고, 그렇지 않으면 그러한 프로그램의 최소 명령어 수이다.

가능한 각 샘플 케이스에 대한 최단 프로그램 몇 가지가 아래에 제시되어 있다.

• 샘플 케이스 #1:

또는

.

• 샘플 케이스 #2:

.

• 샘플 케이스 #3:

.

• 샘플 케이스 #4:

.

프로그램은 가능한 최소 개수의 줄을 포함해야 하지만, Marlin이 이동하는 횟수까지 최소화할 필요는 없다는 점에 유의하라.