#include <iostream>
#include <iomanip>
using namespace std;

const bool PRINTMOVES = false;
const bool PRINTGRID = false;

const int MAX = 100;
const int EMPTY = -1;
const int BLOCKED = -2;

struct lemming {
	char d[4];
	int i;
} lemmings[MAX*MAX];

struct sq {
	int oldl, newl;
	int prevr, prevc;
} grid[MAX][MAX];

int lemmingsLeft;

void printGrid(int n, int m)
{
	for(int i=n-1; i>=0; i--) {
		for(int j=0; j<m; j++) {
			int l = grid[i][j].oldl;
			if (l == EMPTY)
				cout << "---";
			else
				cout << setw(2) << l << lemmings[l].d[lemmings[l].i];
		}
		cout << endl;
	}
	cout << endl;
}
 
void getNewSq(int l, int r, int c, int &newr, int &newc)
{
	switch (lemmings[l].d[lemmings[l].i]) {
	case 'N' : newr = r+1, newc = c; break;
	case 'S' : newr = r-1, newc = c; break;
	case 'E' : newr = r, newc = c+1; break;
	case 'W' : newr = r, newc = c-1; break;
	}
}

void undo(int r, int c)
{
	while (grid[r][c].newl >= 0) {
		int pr = grid[r][c].prevr;
		int pc = grid[r][c].prevc;
		int l = grid[r][c].newl;
		grid[r][c].newl = BLOCKED;
		grid[pr][pc].oldl = l;
		lemmings[l].i = (++lemmings[l].i)%4;	// change this lemmings direction
		r = pr;
		c = pc;
		if (PRINTMOVES) cout << "  move " << l << " back to " << r << ',' << c << endl;
	}
	grid[r][c].newl = BLOCKED;
}

void doTimeStep(int n, int m)
{
	int r, c;
	for(r=0; r<n; r++) {
		for(c=0; c<m; c++) {
			if (grid[r][c].oldl == EMPTY)
				continue;
			int l = grid[r][c].oldl;
			int newr, newc;
			getNewSq(l, r, c, newr, newc);
			if (newr < 0 || newr >=n || newc < 0 || newc >= m) {
				lemmingsLeft--;
				grid[r][c].oldl = EMPTY;
				if (PRINTMOVES) cout << "move " << l << " off the board" << endl;
			}
			else if (grid[newr][newc].newl == EMPTY) {
				grid[newr][newc].newl = l;
				grid[newr][newc].prevr = r;
				grid[newr][newc].prevc = c;
				grid[r][c].oldl = EMPTY;
				if (PRINTMOVES) cout << "move " << l << " to " << newr << ',' << newc << endl;
			}
			else {
				lemmings[l].i = (++lemmings[l].i)%4;	// chane this lemmings direction
				if (PRINTMOVES) cout << "move " << l << " stays at " << r << ',' << c << endl;
				undo(r,c);
				if (grid[newr][newc].newl != BLOCKED) {
					undo(newr, newc);
					grid[newr][newc].newl = BLOCKED;
				}
			}
		}
	}
	for(r=0; r<n; r++) {
		for(c=0; c<m; c++) {
			if (grid[r][c].newl >= 0) {
				if (grid[r][c].oldl != EMPTY) cout << "Hmmm, should have empty old val at " << r << ',' << c << endl;
				grid[r][c].oldl = grid[r][c].newl;
			}
			grid[r][c].newl = EMPTY;
		}
	}
}

int main()
{
	int i, j, k, n, m, icase=0;
	
	cin >> n >> m;
	while (n != 0) {
		icase++;
		k=0;
		for(i=0; i<n; i++) {
			for(j=0; j<m; j++) {
				cin >> lemmings[k].d[0];
				cin >> lemmings[k].d[1];
				cin >> lemmings[k].d[2];
				cin >> lemmings[k].d[3];
				lemmings[k].i = 0;
				grid[i][j].oldl = k;
				grid[i][j].newl = EMPTY;
				k++;
			}
		}
		lemmingsLeft = n*m;
		int t=0;
		if (PRINTGRID) printGrid(n, m);
		while(lemmingsLeft>0) {
			doTimeStep(n, m);
			t++;
			if (PRINTGRID) printGrid(n, m);
		}
		cout << "Case " << icase << ": " << t << endl;

		cin >> n >> m;
	}

	return 0;
}