미로 통과하기 (Small)

로봇 에디슨은 오른손도 눈도 없다. 대신 걸을 때나 방향을 바꿀 때나 항상 왼손을 벽에 대고 있다. 뒤로 걷는 것은 너무 위험하다고 여겨서 절대 뒤로 걷지 않는다. 방향을 바꿀 때는 제자리에서 돌며, 도는 동작은 걸음 수에 넣지 않는다.

에디슨은 $N \times N$ 칸짜리 정사각형 미로 안에 있다. 미로 바깥은 전부 벽으로 둘러싸여 있고, 미로 안에도 벽인 칸이 있다. 에디슨은 빈 칸에서 북, 남, 서, 동으로 붙어 있는 빈 칸으로만 움직인다.

한 걸음을 옮기는 규칙은 이렇다. 지금 바라보는 방향을 기준으로 왼쪽 칸, 앞 칸, 오른쪽 칸, 뒤 칸을 이 순서로 살핀다. 그중 미로 안의 빈 칸이 처음 나오는 방향으로 몸을 돌린 뒤 그 칸으로 한 걸음 옮긴다. 네 방향이 모두 벽이면 한 걸음도 옮기지 못한다.

출발 칸은 미로의 네 모서리 중 하나다. 출발할 때 에디슨이 손을 댈 수 있는 벽은 상하좌우로 붙은 네 칸뿐이고 대각선으로 닿는 여덟 칸은 세지 않으므로, 처음 바라보는 방향은 모서리마다 하나로 정해진다. 왼쪽 위 모서리에서는 동쪽, 오른쪽 위 모서리에서는 남쪽, 오른쪽 아래 모서리에서는 서쪽, 왼쪽 아래 모서리에서는 북쪽을 바라본다. 이 네 방향은 모두 왼손이 미로 바깥 벽에 닿는 방향이고, 왼손이 벽에 닿는 다른 방향으로 출발해도 걸어가는 경로는 똑같다.

에디슨이 10,000걸음 안에 출구 칸에 닿을 수 있는지 판정하고, 닿을 수 있으면 그 경로를 출력한다. 출구 칸에 서기만 하면 미로를 빠져나온 것이다. 출발 칸이 출구와 같다면 움직이지 않고도 빠져나온 것이 된다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 미로의 크기 $N$이 주어진다. 이어지는 $N$개 줄에는 각각 $N$개의 문자가 주어지며, .은 빈 칸이고 #은 벽이다. 그다음 줄에는 네 정수 $sx$, $sy$, $ex$, $ey$가 주어진다. 에디슨은 $sx$행 $sy$열에서 출발하고, $ex$행 $ey$열이 출구다. 왼쪽 위 칸이 $(1, 1)$이다.

제한

• $1 \le T \le 30$
• $2 \le N \le 10$
• $1 \le sx, sy, ex, ey \le N$
• 출발 칸과 출구는 모두 빈 칸이고, 서로 다르다.
• 출발 칸은 미로의 네 모서리 중 하나다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다.

에디슨이 10,000걸음 안에 출구에 닿지 못하면 $y$는 따옴표를 뺀 Edison ran out of energy.이다. 닿으면 $y$는 걸음 수이고, 그다음 줄에 그 걸음 수만큼의 문자로 경로를 출력한다. 각 문자는 동쪽이면 E, 남쪽이면 S, 서쪽이면 W, 북쪽이면 N이다. 동쪽은 열 번호가 1 커지는 방향, 남쪽은 행 번호가 1 커지는 방향이다. 제자리에서 도는 동작을 나타내는 문자는 없으니 출력하지 않는다.

출발한 뒤로는 왼손이 대각선으로 닿는 벽에 기대는 것도 벽을 짚은 것으로 친다. 상하좌우 네 칸으로 제한되는 것은 처음 방향을 정할 때뿐이다.