Problem: The huge maze The Squares has been newly completed in the famous theme park. Evacuation drills must be conducted under the guidance of the fire department, but the time required for the drills cannot be predicted due to the huge maze. Therefore, you decided to develop an evacuation drill simulator based on the following specifications.

As shown in Fig. 1, the giant maze is represented by W × H squares of horizontal W and vertical H. Each square is either a passage (white square), a wall (brown square), or an emergency exit (green square). The circles in the figure represent people, and the lowercase letters (E, W, S, N) in them represent the direction in which the person is facing (north, south, east, and west). The figure is drawn with the upward direction facing north.


<image>

Figure 1




People in the giant maze initially stand facing either north, south, east, or west. Each person attempts to move in 1-second increments at the same time, following the steps below.

1. Look at the right, front, left, and back squares in the direction you are currently facing, and turn to the first vacant aisle or emergency exit you find. If there is no such square, the direction will not change.
2. If the square in front of you is open and not in front of another person, move it. If there are multiple people with the same square in front of you, the selected one will move in the order of the people in that square, east, north, west, and south.



Those who arrive at the emergency exit after moving will evacuate safely and disappear from the maze.

Create a program that inputs the given huge maze and the location information of people and outputs the time when all people finish evacuating. If it takes more than 180 seconds to escape, output NA. Maze and person location information is given by the characters in rows H and columns W. The meaning of each character is as follows.

: Wall
.: Floor
X: Emergency exit
E: People facing east
N: People facing north
W: People facing west
S: People facing south


The boundary between the maze and the outside is either the wall # or the emergency exit X. In addition, there is always one or more people in the huge maze.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by two lines of zeros. Each dataset is given in the following format:


W H
str1
str2
::
strH


The first line gives the horizontal size W of the maze and the vertical size H (1 ≤ W, H ≤ 30). The following H line is given the string stri (length W) that represents the i-th line of the maze.

The number of datasets does not exceed 50.

Output

For each input dataset, the time when all people finish evacuating is output on one line.

Examples

Input

10 3
##########
#E.......X
##########
4 4
####
#N.#
#..X
####
5 5
#####
#N..#
###.X
#S..#
#####
6 6
######
#..#X#
#.EE.#
####N#
#....#
######
8 8
##X#####
#....E.#
#####.##
#.#...##
#.W.#..#
#.#.N#.X
#X##.#.#
########
0 0


Output

8
NA
9
16
10


Input

10 3

E.......X

4 4

N.#
..X

5 5

N..#
.X
S..#

6 6

..#X#
.EE.#
N#
....#

8 8
X#####
....E.#
.##
.#...##
.W.#..#
.#.N#.X
X##.#.#

0 0


Output

8
NA
9
16
10

Solution (in JAVA):

Solution:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;


public class Main {
	
	public static final int NONE = Integer.MAX_VALUE;
	public static final int EAST = 0;
	public static final int NORTH = 1;
	public static final int WEST = 2;
	public static final int SOUTH = 3;
	
	public static final int[][] look = new int[][]{
		{1, 0}, {0, -1}, {-1, 0}, {0, 1}
	};
	
	public static final int[][][] move = new int[][][]{
		{{0, 1}, {1, 0}, {0, -1}, {-1, 0}},
		{{1, 0}, {0, -1}, {-1, 0}, {0, 1}},
		{{0, -1}, {-1, 0}, {0, 1}, {1, 0}},
		{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
	};
		
	public static final int[][] move_dir = new int[][]{
		{SOUTH, EAST, NORTH, WEST},
		{EAST, NORTH, WEST, SOUTH},
		{NORTH, WEST, SOUTH, EAST},
		{WEST, SOUTH, EAST, NORTH}
	};
	
	public static final int WALL = 0;
	public static final int FLAT = 1;
	public static final int EXIT = 2;
	
	public static boolean is_ok(int x, int y, int h, int w){
		if(x < 0 || x >= w || y < 0 || y >= h){
			return false;
		}else{
			return true;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			final int W = sc.nextInt();
			final int H = sc.nextInt();
			
			if(W == 0 && H == 0){
				break;
			}
			
			int map[][] = new int[H][W];
			int people[][] = new int[H][W];
			int next_people[][] = new int[H][W];
			
			for(int i = 0; i < H; i++){
				char[] input = sc.next().toCharArray();
				
				for(int j = 0; j < W; j++){
					switch(input[j]){
					case '#':
						map[i][j] = WALL;
						people[i][j] = NONE;
						break;
					case '.':
						map[i][j] = FLAT;
						people[i][j] = NONE;
						break;
					case 'X':
						map[i][j] = EXIT;
						people[i][j] = NONE;
						break;
					case 'E':
						people[i][j] = EAST;
						map[i][j] = FLAT;
						break;
					case 'W':
						people[i][j] = WEST;
						map[i][j] = FLAT;
						break;
					case 'N':
						people[i][j] = NORTH;
						map[i][j] = FLAT;
						break;
					case 'S':
						people[i][j] = SOUTH;
						map[i][j] = FLAT;
						break;	
					}
				}
			}
			
			boolean over = true;
			int end_time = 1;
			for(int time = 1; time <= 180; time++){
				//change_look
				for(int i = 0; i < H; i++){
					for(int j = 0; j < W; j++){
						if(people[i][j] != NONE){
							final int dir = people[i][j];
							
							for(int looking : move_dir[dir]){
								int[] move_d = look[looking];
								
								final int nx = j + move_d[0];
								final int ny = i + move_d[1];
								
								if(!is_ok(nx, ny, H, W)){
									continue;
								}else if(map[ny][nx] == WALL){
									continue;
								}else if(people[ny][nx] != NONE){
									continue;
								}
								
								people[i][j] = looking;
								break;
							}
						}
					}
				}
				
				//move
				for(int i = 0; i < H; i++){
					for(int j = 0; j < W; j++){
						if(map[i][j] == WALL){
							continue;
						}else if(people[i][j] != NONE){
							continue;
						}
						
						boolean flag = false;
						for(int dir : move_dir[NORTH]){
							int[] looking = look[dir];
							final int ref = (4 + dir - 2) % 4;
							
							final int nx = j + looking[0];
							final int ny = i + looking[1];
							
							if(!is_ok(nx, ny, H, W)){
								continue;
							}else if(map[ny][nx] == WALL){
								continue;
							}else if(people[ny][nx] == NONE){
								continue;
							}else if(people[ny][nx] != ref){
								continue;
							}
							
							next_people[i][j] = people[ny][nx];
							next_people[ny][nx] = NONE;
							flag = true;
							break;
						}
						
						if(!flag){
							next_people[i][j] = people[i][j];
						}
					}
				}
				
				//remove
				for(int i = 0; i < H; i++){
					for(int j = 0; j < W; j++){
						if(map[i][j] != EXIT){
							continue;
						}else if(next_people[i][j] == NONE){
							continue;
						}
						
						next_people[i][j] = NONE;
					}
				}
				
				//is_end?
				boolean is_end = true;
				//remove
				END:
				for(int i = 0; i < H; i++){
					for(int j = 0; j < W; j++){
						if(map[i][j] == WALL){
							continue;
						}else if(next_people[i][j] == NONE){
							continue;
						}
						
						is_end = false;
						break END;
					}
				}
				
				if(is_end){
					over = false;
					end_time = time;
					break;
				}
				
				//update
				for(int i = 0; i < H; i++){
					for(int j = 0; j < W; j++){
						people[i][j] = next_people[i][j];
					}
				}
			}
			
			if(over){
				System.out.println("NA"); 
			}else{
				System.out.println(end_time);
			}
		}
		
	}

}