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.*;
public class Main {
	static int h;
	static int w;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while(true) {
			w = sc.nextInt();
			h = sc.nextInt();
			if(w == 0 && h == 0) break;
			char[][] map;
			boolean[][] alMove;
			map = new char[h][w];
			alMove = new boolean[h][w];
			for(int i = 0; i < h; i++) {
				map[i] = sc.next().toCharArray();
			}
			int i = 0;
			for(i = 0; i <= 180; i++) {
				boolean check = false;
				for(int j = 0; j < h; j++) {
					for(int k = 0; k < w; k++) {
						if(map[j][k] == '.' || map[j][k] == 'X' || map[j][k] == '#') continue;
						if(map[j][k] == 'E') {
							check = true;
							if     (rcheck(j+1,k) && (map[j+1][k] == '.' || map[j+1][k] == 'X')) {
								map[j][k] = 'S';
							}
							else if(rcheck(j,k+1) && (map[j][k+1] == '.' || map[j][k+1] == 'X')) {
								map[j][k] = 'E';
							}
							else if(rcheck(j-1,k) && (map[j-1][k] == '.' || map[j-1][k] == 'X')) {
								map[j][k] = 'N';
							}
							else if(rcheck(j,k-1) && (map[j][k-1] == '.' || map[j][k-1] == 'X')) {
								map[j][k] = 'W';
							}
						}
						else if(map[j][k] == 'N') {
							check = true;
							if     (rcheck(j,k+1) && (map[j][k+1] == '.' || map[j][k+1] == 'X')) {
								map[j][k] = 'E';
							}
							else if(rcheck(j-1,k) && (map[j-1][k] == '.' || map[j-1][k] == 'X')) {
								map[j][k] = 'N';
							}
							else if(rcheck(j,k-1) && (map[j][k-1] == '.' || map[j][k-1] == 'X')) {
								map[j][k] = 'W';
							}
							else if(rcheck(j+1,k) && (map[j+1][k] == '.' || map[j+1][k] == 'X')) {
								map[j][k] = 'S';
							}
							
						}
						else if(map[j][k] == 'W') {
							check = true;
							if     (rcheck(j-1,k) && (map[j-1][k] == '.' || map[j-1][k] == 'X')) {
								map[j][k] = 'N';
							}
							else if(rcheck(j,k-1) && (map[j][k-1] == '.' || map[j][k-1] == 'X')) {
								map[j][k] = 'W';
							}
							else if(rcheck(j+1,k) && (map[j+1][k] == '.' || map[j+1][k] == 'X')) {
								map[j][k] = 'S';
							}
							else if(rcheck(j,k+1) && (map[j][k+1] == '.' || map[j][k+1] == 'X')) {
								map[j][k] = 'E';
							}
						}
						else if(map[j][k] == 'S') {
							check = true;
							if     (rcheck(j,k-1) && (map[j][k-1] == '.' || map[j][k-1] == 'X')) {
								map[j][k] = 'W';
							}
							else if(rcheck(j+1,k) && (map[j+1][k] == '.' || map[j+1][k] == 'X')) {
								map[j][k] = 'S';
							}
							else if(rcheck(j,k+1) && (map[j][k+1] == '.' || map[j][k+1] == 'X')) {
								map[j][k] = 'E';
							}
							else if(rcheck(j-1,k) && (map[j-1][k] == '.' || map[j-1][k] == 'X')) {
								map[j][k] = 'N';
							}
						}
					}
				}
				if(!check) break;
				for(int j = 0; j < h; j++) {
					Arrays.fill(alMove[j], false);
				}
				for(int j = 0; j < h; j++) {
					IN:for(int k = 0; k < w; k++) {
						if(map[j][k] != '.' && map[j][k] != 'X') continue;
						if(map[j][k] == '.') {
							if    (rcheck(j,k+1) && !alMove[j][k] && !alMove[j][k+1] && map[j][k+1] == 'W') {
								map[j][k+1] = '.';
								map[j][k] = 'W';
								alMove[j][k] = true;
								alMove[j][k+1] = true;
								continue IN;
							}
							else if    (rcheck(j-1,k) && !alMove[j][k] && !alMove[j-1][k] && map[j-1][k] == 'S') {
								map[j-1][k] = '.';
								map[j][k] = 'S';
								alMove[j][k] = true;
								alMove[j-1][k] = true;
								continue IN;
							}
							else if    (rcheck(j,k-1) && !alMove[j][k] && !alMove[j][k-1] && map[j][k-1] == 'E') {
								map[j][k-1] = '.';
								map[j][k] = 'E';
								alMove[j][k] = true;
								alMove[j][k-1] = true;
								continue IN;
							}
							else if    (rcheck(j+1,k) && !alMove[j][k] && !alMove[j+1][k] && map[j+1][k] == 'N') {
								map[j+1][k] = '.';
								map[j][k] = 'N';
								alMove[j][k] = true;
								alMove[j+1][k] = true;
								continue IN;
							}
						}
						else if(map[j][k] == 'X') {
							if(rcheck(j,k+1) && map[j][k+1] == 'W' && !alMove[j][k] && !alMove[j][k+1]) {
								map[j][k+1] = '.';
								alMove[j][k] = true;
								alMove[j][k+1] = true;
								continue IN;
							}
							else if(rcheck(j-1,k) && map[j-1][k] == 'S' && !alMove[j][k] && !alMove[j-1][k]) {
								map[j-1][k] = '.';
								alMove[j][k] = true;
								alMove[j-1][k] = true;
								continue IN;
							}
							else if(rcheck(j,k-1) && map[j][k-1] == 'E' && !alMove[j][k] && !alMove[j][k-1]) {
								map[j][k-1] = '.';
								alMove[j][k] = true;
								alMove[j][k-1] = true;
								continue IN;
							}
							else if(rcheck(j+1,k) && map[j+1][k] == 'N' && !alMove[j][k] && !alMove[j+1][k]) {
								map[j+1][k] = '.';
								alMove[j][k] = true;
								alMove[j+1][k] = true;
								continue IN;
							}
						}
					}
				}
			}
			if(i <=  180) {
				System.out.println(i);
			}
			else {
				System.out.println("NA");
			}
		}
	}
	
	public static boolean rcheck(int a, int b) {
		if(a < 0 || b < 0 || a >= h || b >= w) return false;
		return true;
	}
}