The Worm Turns

Worm is an old computer game. It comes in many versions, but they all involve steering a "worm" around the screen while trying not to run the worm into itself or into an obstacle.

Here we simulate a heavily simplified version. The game is played on a $50 \times 50$ board whose cells are numbered so that the upper-left cell is $(1, 1)$. The first coordinate is the row $r$ and the second is the column $c$, with $1 \le r \le 50$ and $1 \le c \le 50$.

The worm is a chain of 20 connected cells. Two cells are connected when they are adjacent horizontally or vertically. At the start the worm is stretched out horizontally, occupying $(25, 11)$ through $(25, 30)$, with its head at $(25, 30)$.

On each move the worm advances one cell East (E), West (W), North (N), or South (S). E and W change the column by $+1$ and $-1$; S and N change the row by $+1$ and $-1$. The worm never moves back onto itself, so from the starting position a W move is impossible. Because of this, the only two cells that change on any move are the head and the tail: the head advances one cell and the tail is pulled forward by one cell. In particular, the head may move into the cell that the tail vacates on the very same move.

You are given a sequence of moves and must simulate them until one of the following happens:

• the worm runs into itself,
• the worm runs off the board, or
• the worm completes its entire list of moves.

In the first two cases, ignore the remaining moves in the list.

The input contains several test cases. Each test case is given on two lines. The first line contains an integer $n$ ($n < 100$), the number of moves. A line containing $n = 0$ marks the end of the input and must not be processed. The second line contains exactly $n$ characters, each one of E, W, N, or S with no separating spaces, giving the sequence of moves.

For each test case, print exactly one line. Taking the first move as move 1 and letting $m$ be the move number you determine, the line must be exactly one of the following three:

• The worm ran into itself on move m.
• The worm ran off the board on move m.
• The worm successfully made all m moves.