Cross the maze (large)

Edison the robot has no right hand and no eyes. Whether he walks or turns in place, he always keeps his left hand on a wall. He thinks walking backward is too dangerous, so he never does it.

Edison is inside a square maze of $N \times N$ cells. The maze is closed off by walls on the outside, and some cells inside the maze are walls as well. Edison moves between empty cells in the four directions north, south, west and east.

To get out, Edison keeps his left hand on the wall and follows it. Standing on a cell, he looks at the directions relative to the way he is facing in this order: left, forward, right, back. He turns toward the first of them that holds an empty cell, then walks one cell that way. The direction he just walked becomes the direction he faces. If all four directions are walls, he cannot move any more.

Decide whether Edison reaches the exit cell in at most 10,000 steps, and print the path when he does. Standing on the exit cell counts as getting out of the maze.

The first line contains the number of test cases $T$. The first line of each test case contains the size of the maze $N$. Each of the next $N$ lines contains $N$ characters. . is an empty cell and # is a wall. The next line contains four integers $sx$, $sy$, $ex$, $ey$. Edison starts on row $sx$, column $sy$, and the exit is on row $ex$, column $ey$. The top left cell is at position $(1, 1)$.

Limits

• $1 \le T \le 30$
• $2 \le N \le 100$
• $1 \le sx, sy, ex, ey \le N$
• The starting cell $(sx, sy)$ is one of the four corners of the maze.
• The starting cell and the exit are both empty cells, and they are different cells.

For each test case, print one line in the form Case #x: y. Here $x$ is the test case number, starting from $1$. If Edison does not reach the exit within 10,000 steps, $y$ is Edison ran out of energy. without the quotes. Otherwise $y$ is the number of steps, and the next line holds $y$ characters describing the path. In the path, E is east, S is south, W is west and N is north. Turning in place is neither counted nor printed.

At the start, Edison's left hand touches a wall among the four cells directly above, below, left of and right of him, or the outer wall of the maze. A cell that touches only at a diagonal does not count.

Because the starting cell is a corner, two of the four directions are always the outer wall. So even when several starting orientations put his left hand on a wall, the rule above produces the same path for all of them.