/**
 * Solution to "Lemmings"
 */
import java.util.*;

public class Lemmings {

/** 
 * Utility class -- holds information about a single lemming, including:
 *     - id -- its unique identifier (used for debugging only)
 *     - its agenda, a four-letter permutation of "NEWS"
 *     - row, col -- its current position on the grid
 *     - nextRow, nextCol -- its desired next position on the grid 
 *        according to the currently active direction in its agenda
 *     - pos -- the position in the "agenda" string of the current direction
 *     - alive -- an indicator of whether or not it has fallen off the grid
 *     - counter -- static variable used for generating "id"
 */
static class Lemming {
   public int id;
   public String agenda;
   public int pos,row,col,nextRow,nextCol;
   public boolean alive;
   public static int counter;

   /**
    * Create a new lemming with a unique id, a specified starting location,
    * and a specified agenda. 
    */
   public Lemming(int row, int col, String agenda) {
      this.row = row;
      this.col = col;
      this.agenda = agenda;

      // Determine its desired next position:
      findNext();
      pos = 0;
      alive = true;
      id = counter++;
//System.out.println("Created lemming " + id + " at " + row + "," + col +
//" with agenda " + agenda);
   }


   public char dir() {
      return agenda.charAt(pos);
   }


   public void nextDir() {
      pos = (pos+1) % 4;
   }

   public void findNext() {
      char d = dir();
      nextRow = row;
      nextCol = col;
      switch (d) {
         case 'N': nextRow++; break;
         case 'S': nextRow--; break;
         case 'E': nextCol++; break;
         case 'W': nextCol--; break;
      }
   }

   public void move() {
      if (alive) {
         row = nextRow;
         col = nextCol;
         if (row >= 0 && row < n && col >= 0 && col < m)
            findNext();
         else
            alive = false; 
      }
   }
}
   

/**
 * Main program variables:
 *     in -- for input
 *     m,n -- grid dimensions
 *     lem -- grid of lemmings (initially filled with live lemmings)
 *     live -- list of the live lemmings (for faster processing; avoids
 *         the need to scan the array every time)
 *     seek -- grid containing the number of lemmings seeking to enter
 *         each square at each step. Only grid locations with a seek
 *         value of 1 can accommodate a new lemming moving into that square.
 */
   public static Scanner in = new Scanner(System.in);
   public static int m, n;
   public static Lemming[][] lem; 
   public static ArrayList<Lemming> live;
   public static int[][] seek;
   
   public static void main(String[] args) {
      n = in.nextInt();
      m = in.nextInt();
      int caseNum = 0;
      Lemming dummy = new Lemming(0,0,"XXXX");
      dummy.alive = false;
      while (m != 0 || n != 0) {
         int time = 0;
         caseNum++;
         Lemming.counter = 0;
         lem = new Lemming[n][m];
         live = new ArrayList<Lemming>();
         for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
               String a = in.next();
               lem[i][j] = new Lemming(i,j,a);
               live.add(lem[i][j]);
            }
         }

         int count = n*m;
         // Basic processing loop: as long as the count of live lemmings is
         // nonzero,
         //    zero out the "seek" array
         //    for each live lemming in the lemming array, find its
         //       desired "next" location and add one to the seek value
         //       for that location (unless it will fall off, in which
         //           case we immediately process it)
         //    for each live lemming in the lemming array, see if its
         //       desired next location has a seek value of 1;
         //       if so, move it; if not, find the next direction in its
         //        agenda
         while (count > 0) {
            time++;
            seek = new int[n][m];
            // See where each lemming wants to go:
            for (Lemming l: live) {
               int nxtR = l.nextRow;
               int nxtC = l.nextCol;

//System.out.println("lemming " + l.id + " at " + l.row + "," + l.col 
//+ " wants to go to " + nxtR + "," + nxtC);

               if (nxtR >= 0 && nxtR < n && nxtC >= 0 && nxtC < m) {
                  seek[nxtR][nxtC]++;
               }
               else {
                  l.alive = false;
                  count--;
//System.out.println("lemming " + l.id + " takes the plunge!");
               }
            }

            // Purge the non-alive lemmings (nothing can prevent
            // these lemmings from moving):
            int i = 0;
            while ( i < live.size()) {
               Lemming l = live.get(i);
               if (!l.alive)
                  live.remove(i);
               else
                  i++;
            }

// Now loop over the lemmings and the "seek" data to see if there are
// any lemmings who are blocked via a chain of "seeks" that end in
// a blocked square. If a lemming can't move, change the seek value
// of the square it's on to something illegal, e.g., 5. Whenever a blockage
// is found, we need to iterate once more through this loop.

            boolean blockage = true;
            while (blockage) {
               blockage = false;
               for (Lemming l: live) {
                  int temp = seek[l.nextRow][l.nextCol];
                  if (temp > 1 && seek[l.row][l.col] <= 4) {
                     blockage = true;
                     seek[l.row][l.col] = 5;
                  }
               }
            }

            // Now move the remaining lemmings to their new positions
            // or turn them in their new directions:
            for (Lemming l: live) {
               int r = l.nextRow;
               int c = l.nextCol;
               if (seek[r][c] <= 1) {
                  l.move();
               }
               else {
                  l.nextDir();
                  l.findNext();
               }
            }
/*
            for (int i = 0; i < n; i++) {
               for (int j = 0; j < m; j++) {
                  Lemming l = temp[i][j];
                  if (l == null) {
                     lem[i][j] = dummy;
                  }
                  else {
                     int r = l.row;
                     int c = l.col;
                     lem[r][c] = l;
                  }
               }
            }
*/
         }
         System.out.println("Case " + caseNum+ ": "+time);
         n = in.nextInt();
         m = in.nextInt();
      }
   }
}
