Lemmings, Lemmings Everywhere. But Not For Long.

On an $n \times m$ board there is a lemming on every square. Every second the lemmings all try to move one square north, south, east, or west, following the rules below. Each lemming has an agenda, a permutation of the four directions (for example NWES).

1. Each lemming's current direction $D$ starts as the first direction in its agenda.
2. At each time step, each lemming tries to move one square in its direction $D$. For a lemming $L$:
   1. If $D$ would take $L$ off the board, $L$ leaves the board (the world has one fewer lemming). Otherwise $L$'s target is another square.
   2. If $L$'s target square is empty, or is about to become empty because the lemming on it is leaving, and no other lemming is also trying to move onto that square, then $L$ moves onto it. In this case $L$ keeps the same direction $D$ for the next step.
   3. Otherwise (another lemming is also trying to move onto $L$'s target square, or that square holds a lemming that cannot move), $L$ stays put and advances $D$ to the next direction in its agenda, wrapping around if necessary.

Two lemmings that want to exchange squares may do so, unless some other lemming is also trying to move onto one of their two squares (in which case all three stay put). The lemmings keep moving until every one of them has left the board. Determine how many steps this takes.

The input consists of several test cases. Each test case begins with a line containing two positive integers $n$ and $m$, the number of rows and columns; each is at most $100$. The board is oriented so that square $(0, 0)$ is the southwest corner and square $(0, m - 1)$ is the southeast corner. Then come the agendas of the $nm$ lemmings, each a permutation of the string NESW, separated by single spaces, with $16$ agendas per line (except possibly the last). The agendas are assigned to lemmings row by row: the first to the lemming on $(0, 0)$, the second to $(0, 1)$, and so on. The line 0 0 follows the last test case and terminates the input.

For each test case, output one line containing the case number followed by the number of steps until the last lemming or lemmings fall off the board, in the format

Case k: steps

Use only single spaces to separate the items on the line.