Cross the maze (Small)

Edison the robot has no right hand and no eyes. Whether he walks or turns, he always keeps his left hand on a wall. He thinks walking backward is far too dangerous, so he never does it. To go back he turns around in place, and a turn does not count as a step.

Edison is inside a square maze of $N \times N$ cells. The maze is surrounded by walls on the outside, and some cells inside the maze are walls as well. Edison moves only from an empty cell to an empty cell next to it, north, south, west or east.

One step works like this. From the direction he currently faces, he checks the cell on his left, then the cell straight ahead, then the cell on his right, then the cell behind him, in that order. He turns toward the first of those directions that holds an empty cell inside the maze and walks one cell that way. If all four are walls, he cannot move at all.

The starting cell is one of the four corners of the maze. At the start the only walls Edison can touch are the ones on the 4 cells next to him, not on the 8 cells around him, so the direction he faces at the start is fixed for each corner. He faces east from the top-left corner, south from the top-right corner, west from the bottom-right corner, and north from the bottom-left corner. Each of those puts his left hand on the outer wall of the maze, and starting from any other facing that puts his left hand on a wall gives the same walk.

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 is enough to get out of the maze. If the starting cell is the exit, Edison gets out without moving.

The first line contains the number of test cases, $T$. The first line of each test case contains $N$, the size of the maze. The next $N$ lines contain $N$ characters each, where . is an empty cell and # is a wall. The line after that 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 $(1, 1)$.

Limits

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

For each test case print one line in the form Case #x: y, where $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 that many characters describing the path: E for east, S for south, W for west, N for north. East increases the column number by 1, and south increases the row number by 1. There is no character for turning around, so do not print one.

After the start, a wall his left hand reaches diagonally also counts as leaning on the wall. The restriction to the 4 cells next to him applies only when the first direction is chosen.