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 CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

int w, h;

// 0:→, 1:↑, 2:←, 3:↓
int dx[4] = {+1,0,-1,0};
int dy[4] = {0,-1,0,+1};

void debug(const vector<string>& s, int t){
	char H[256] = {0};
	H['E'] = '>'; H['W'] = '<'; H['N'] = '^'; H['S'] = 'v';
	H['X'] = 'X'; H['.'] = '.'; H['#'] = '#';
	
	cout << "time : " << t << endl;
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			cout << H[s[y][x] ];
		}
		cout << endl;
	}
	cout << endl;
}

// 位置 (px,py), 向き d, の人が空いているマスを探し, 最初に見つけた向きを返す.
// ないときは d を返す. 
int search(const vector<string>& s, int px, int py, int d){
	// 右, 前, 左, 後ろの順に調べる.
	int f[4] = {+3,0,+1,+2};
	
	for(int i=0 ; i < 4 ; i++ ){
		int next_d = (d + f[i]) % 4;
		int mx = px + dx[next_d];
		int my = py + dy[next_d];
		
		if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
		 
		if( s[my][mx] == '.' || s[my][mx] == 'X' ){
			return next_d;
		}
	}
	return d;
}

bool is_person(char c){
	return ( c == 'E' || c == 'W' || c == 'N' || c == 'S');
}

int main(){
	char H[256] = {0};
	H['E'] = 0; H['N'] = 1; H['W'] = 2; H['S'] = 3;
	H[0] = 'E'; H[1] = 'N'; H[2] = 'W'; H[3] = 'S';
	
	while( cin >> w >> h, w || h ){
		vector<string> s(h);
		for(int y=0 ; y < h ; y++ ){
			cin >> s[y];
		}
		//debug( s , 0 );
		// N := 人の数
		int N=0;
		// 人の数を数える.
		for(int y=0 ; y < h ; y++ ){
			for(int x=0 ; x < w ; x++ ){
				if( is_person(s[y][x]) ) N++;
			}
		}
		int ans = -1;
		for(int t=1 ; t <= 180 ; t++ ){
			for(int y=0 ; y < h ; y++ ){
				for(int x=0 ; x < w ; x++ ){
					// (x,y)が人だったら向きを変える
					if( is_person(s[y][x]) ){
						int d = H[ s[y][x] ];
						int next_d = search( s , x , y , d );
						s[y][x] = H[next_d];
					}
				}
			}
			
			vector<string> s_ = s;
			bool cp[100][100] = {false};
			for(int y=0 ; y < h ; y++ ){
				for(int x=0 ; x < w ; x++ ){
					// (x,y) が移動可能なマス かつ まだ誰も移動していなければ調べる.
					if( s[y][x] == '.' || s[y][x] == 'X'){
						// 優先順位は マス(x,y) の右,上,左,下 の順.
						for(int i=0 ; i < 4 ; i++ ){
							int mx = x + dx[i];
							int my = y + dy[i];
							
							if( mx < 0 || my < 0 || mx >= w || my >= h ) continue;
							
							// (mx,my) にいる人が (x,y) に移動する. (x,y) が出口'X' なら人は消える.
							if( is_person(s[my][mx]) && abs(i-H[s[my][mx]]) == 2 ){
								if( s[y][x] == 'X' ){
									s_[my][mx] = '.';
									cp[my][mx] = true;
									N--;
								}else{
									s_[my][mx] = '.';
									s_[y][x] = s[my][mx];
									cp[y][x] = true;
									cp[my][mx] = true;
								}
								break;
							}
						}
					}
					if( !cp[y][x] ) s_[y][x] = s[y][x];
				}
			}
			s = s_;
			//debug( s , t );
			if( N == 0 ){
				ans  = t;
				break;
			}
		}
		if( ans == -1 ){
			cout << "NA" << endl;
		}else{
			cout << ans << endl;
		}
	}
}