미로 건너기

로봇 Edison에게는 오른손도 눈도 없다. 용감한 로봇인 그는 걷거나 방향을 바꿀 때에도 항상 왼손을 벽에 댄다. 뒤로 걷는 것은 너무 위험하다고 생각하기 때문에 Edison은 뒤로 걷지 않는다.

Edison이 외부가 벽으로 둘러싸인 NxN개의 정사각형 칸으로 이루어진 정사각형 미로 안에 있음을 깨달았다고 가정하자. 미로 안에서도 일부 칸은 벽이다. Edison은 비어 있는 두 칸 사이를 북쪽, 남쪽, 서쪽, 동쪽의 네 방향으로만 이동할 수 있다. 미로에서 나가기 위해 그는 계획을 세운다. 왼손을 벽에 대고 벽을 따라 이동한다.

질문은 Edison이 최대 10,000걸음 안에 미로에서 나갈 수 있는가이다. 가능하다면 경로를 출력하라. 미로에서 나가기 위해서는 출구 칸에 있기만 하면 된다. 시작 칸이 출구와 같다면 Edison은 이동할 필요 없이 바로 미로에서 나갈 수 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 30. 1 ≤ sx, sy, ex, ey ≤ N. 시작 칸과 미로의 출구는 항상 빈 칸이다. 그리고 시작 칸과 미로의 출구는 같지 않다.

테스트 세트 1 - 공개

2 ≤ N ≤ 10.

테스트 세트 2 - 비공개

2 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N으로 시작한다. N은 미로의 크기이다. 이어지는 N개의 줄에는 각 줄마다 '.' 또는 '#'일 수 있는 N개의 문자가 주어진다. '.'은 빈 칸이고, '#'은 벽이다. 그다음 줄에는 네 정수 sx, sy, ex, ey가 주어진다. (sx, sy)는 Edison이 시작 칸인 sx행 sy열에 서 있음을 의미하고, (ex, ey)는 미로의 출구이다. (sx, sy)는 미로의 4개 모서리 중 하나임이 보장되며, 처음에 Edison은 인접한 칸 4개에 있는 벽에만 닿을 수 있다(8개가 아님). (ex, ey)는 미로 안 어디에나 있을 수 있다. 왼쪽 위 모서리의 위치는 (1,1)임에 유의하라.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, Edison이 최대 10,000걸음 안에 미로의 출구에 도달할 수 없다면 y는 따옴표를 제외한 "Edison ran out of energy."이다. 그렇지 않다면 y는 걸음 수여야 하며, 이어지는 다른 한 줄에는 경로를 나타내는 y개의 문자를 출력한다(각 문자는 동쪽이면 E, 남쪽이면 S, 서쪽이면 W, 북쪽이면 N이어야 한다). 방향을 바꾸는 것을 나타내는 문자는 없다. 방향을 바꾸는 데 드는 걸음은 고려하지 않으므로, Edison이 미로를 건너는 경로만 출력하라.

참고: 2번째 테스트 케이스에서 Edison은 시작 칸으로부터 아래로 1칸 이동한 후에도 왼손을 (1,2) 칸의 벽에 댈 수 있다. 세 번째 테스트 케이스에서 Edison은 처음에 (2,2) 칸의 벽에 닿을 수 없으므로 첫걸음에 동쪽으로 가야 한다.