팩맨

청호가 팩맨 게임을 하다가 팩맨 한 마리가 둘로 갈라지는 장면을 봤다. 두 팩맨은 서로 다른 칸에 있지만 조이스틱 하나에 똑같이 반응한다. 북쪽으로 조작하면 두 마리가 모두 북쪽으로 한 칸 움직이고, 동쪽으로 조작하면 두 마리가 모두 동쪽으로 한 칸 움직인다.

미로는 $M \times N$ 격자다. 팩맨이 들어가려는 칸에 벽이 있으면 그 팩맨은 제자리에 남는다. 유령을 마주친 팩맨은 그 자리에서 잡아먹히므로, 두 팩맨 중 한 마리라도 유령이 있는 칸으로 들어가게 되는 방향은 아예 조작하지 않는다. 유령은 제자리에 가만히 있는다. 미로 밖으로 나간 팩맨은 반대쪽 끝에서 다시 나타난다.

두 팩맨은 서로를 막지 않는다. 한 번의 조작을 끝낸 뒤 두 마리가 같은 칸에 있으면 합쳐진 것이고, 서로 지나치며 자리만 맞바꾼 것은 합쳐진 것이 아니다.

청호는 두 팩맨을 최대한 빨리 한 칸으로 모으려고 한다. 필요한 조작의 최소 횟수와 그때 조작한 방향의 순서를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 미로의 행 개수 $M$과 열 개수 $N$ ($2 \le M, N \le 50$)이 주어진다. 이어지는 $M$개의 줄에는 미로가 한 줄에 $N$개의 문자로 주어진다. 각 문자의 뜻은 다음과 같다.

• P는 팩맨
• X는 벽
• G는 유령
• .은 빈칸

미로마다 P는 정확히 두 개 있고, 두 팩맨의 위치는 서로 다르다.

각 테스트 케이스마다 한 줄에 답을 출력한다.

두 팩맨을 한 칸으로 모을 수 있으면 최소 조작 횟수를 출력하고, 공백 한 칸을 둔 다음 조작한 방향을 순서대로 이어 붙여 출력한다. 북쪽은 N, 동쪽은 E, 남쪽은 S, 서쪽은 W로 나타낸다. 최소 횟수를 만드는 조작 순서가 여럿이면 사전순으로 가장 앞서는 것을 출력한다. 문자의 사전순은 E, N, S, W 순서다.

모을 수 없으면 IMPOSSIBLE을 출력한다.