레밍, 사방이 레밍. 하지만 오래가진 않는다.

$n \times m$ 판의 모든 칸에 레밍이 한 마리씩 있다. 매초 모든 레밍은 아래 규칙에 따라 동서남북 중 한 칸으로 움직이려고 한다. 각 레밍은 네 방향의 순열인 의제(agenda) 를 하나씩 가진다(예: NWES).

1. 각 레밍의 현재 방향 $D$는 의제의 첫 방향으로 시작한다.
2. 매 시간 단계마다 각 레밍은 방향 $D$로 한 칸 움직이려고 한다. 레밍 $L$에 대해:
   1. $D$가 $L$을 판 밖으로 내보내면 $L$은 판을 떠난다(레밍이 하나 줄어든다). 그렇지 않으면 $L$의 목표는 다른 칸이다.
   2. $L$의 목표 칸이 비어 있거나, 그 칸의 레밍이 떠나 곧 비게 되고, 또한 다른 어떤 레밍도 그 칸으로 움직이려 하지 않으면 $L$은 그 칸으로 이동한다. 이때 $L$은 다음 단계에서도 같은 방향 $D$를 유지한다.
   3. 그 밖의 경우(다른 레밍도 $L$의 목표 칸으로 움직이려 하거나, 그 칸에 움직일 수 없는 레밍이 있는 경우) $L$은 제자리에 머무르고 $D$를 의제의 다음 방향으로 바꾼다(필요하면 처음으로 돌아간다).

서로 칸을 맞바꾸려는 두 레밍은 자리를 바꿀 수 있다. 단, 다른 레밍이 그 두 칸 중 하나로 움직이려 하면 세 마리 모두 제자리에 머무른다. 레밍들은 모두 판을 떠날 때까지 계속 움직인다. 그렇게 되기까지 몇 단계가 걸리는지 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 행과 열의 개수를 나타내는 두 양의 정수 $n$과 $m$이 적힌 줄로 시작하며, 각 값은 최대 $100$이다. 판은 칸 $(0, 0)$이 남서쪽 모서리, 칸 $(0, m - 1)$이 남동쪽 모서리가 되도록 놓인다. 이어서 $nm$마리 레밍의 의제가 주어지며, 각 의제는 문자열 NESW의 순열이고 한 칸 띄어 구분된다. 한 줄에 의제가 $16$개씩 있다(마지막 줄은 그렇지 않을 수 있다). 의제는 행 순서대로 레밍에 배정된다. 즉 첫 번째 의제는 $(0, 0)$의 레밍에, 두 번째는 $(0, 1)$의 레밍에, 이런 식이다. 마지막 테스트 케이스 다음에 0 0 줄이 오며 입력을 끝낸다.

각 테스트 케이스에 대해, 케이스 번호와 마지막 레밍(들)이 판에서 떨어질 때까지 걸린 단계 수를 다음 형식으로 한 줄에 출력한다.

Case k: steps

한 줄의 항목들은 오직 하나의 공백으로만 구분한다.