The Squares

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.

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

inputFormat

inputs the given huge maze and the location information of people and

outputFormat

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

样例

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

8
NA
9
16
10

</p>