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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from sys import stdin

def main():
	head = [[8, 1, 2, 4], [1, 2, 4, 8], [2, 4, 8, 1], [4, 8, 1, 2]]
	while True:
		(W, H) = map(int, stdin.readline().split())
		m = [[0] * W for _ in range(H)]
		ps = []
		if not (W or H):
			break
		for h in range(H):
			s = stdin.readline()
			for w in range(W):
				if s[w] in ['.', 'X', 'E', 'N', 'W', 'S']:
					m[h][max(0, w - 1)] |= 1
					m[min(H - 1, h + 1)][w] |= 2
					m[h][min(W - 1, w + 1)] |= 4
					m[max(0, h - 1)][w] |= 8
				if s[w] in ['E', 'N', 'W', 'S']:
					ps.append([h, w, ['E', 'N', 'W', 'S'].index(s[w])])
				if s[w] == 'X':
					m[h][w] |= 16
		if W <= 2 or H <= 2:
			print(1)
			continue
		ttt = 0
		while True:
			ttt += 1
			if ttt > 180:
				print('NA')
				break
			dest = []
			positions = [a[:2] for a in ps]
			for (pi, p) in enumerate(ps):
				for i in range(4):
					if head[p[2]][i] & m[p[0]][p[1]]:
						d = head[p[2]][i]
						if d == 1 and (not [p[0], p[1] + 1] in positions):
							p[2] = 0
							dest.append([pi, 2, p[0], p[1] + 1])
							break
						elif d == 2 and (not [p[0] - 1, p[1]] in positions):
							p[2] = 1
							dest.append([pi, 3, p[0] - 1, p[1]])
							break
						elif d == 4 and (not [p[0], p[1] - 1] in positions):
							p[2] = 2
							dest.append([pi, 0, p[0], p[1] - 1])
							break
						elif d == 8 and (not [p[0] + 1, p[1]] in positions):
							p[2] = 3
							dest.append([pi, 1, p[0] + 1, p[1]])
							break
				else:
					dest.append([pi, p[2] + 2 & 3, p[0], p[1]])
			dest = sorted(dest, key=lambda x: (x[2:], x[1]))
			dellist = []
			for (pi, d, dy, dx) in dest:
				if not [dy, dx] in positions:
					positions.append([dy, dx])
					ps[pi][:2] = [dy, dx]
				if m[ps[pi][0]][ps[pi][1]] & 16:
					dellist.append(pi)
			for idx in sorted(dellist)[::-1]:
				del ps[idx]
			if not len(ps):
				print(ttt)
				break
main()


dd = ((1, 0), (0, -1), (-1, 0), (0, 1))
ENWS = 'ENWS'
ds = [-1, 0, 1, 2]
ss = [2, 3, 0, 1]
while 1:
	(W, H) = map(int, input().split())
	if W == H == 0:
		break
	S = [input() for i in range(H)]
	ps = []
	U = [[-1] * W for i in range(H)]
	for i in range(H):
		for (j, c) in enumerate(S[i]):
			if c in ENWS:
				ps.append([i, j, ENWS.index(c)])
				U[i][j] = 1
			elif c == '#':
				U[i][j] = W * H
	rest = len(ps)
	t = 0
	while rest > 0 and t <= 180:
		for p in ps:
			(y, x, c) = p
			if c == -1:
				continue
			for d in ds:
				(dx, dy) = dd[(c + d) % 4]
				nx = x + dx
				ny = y + dy
				if U[ny][nx] == -1:
					p[2] = (c + d) % 4
					break
		ps.sort(key=lambda x: ss[x[2]])
		qs = []
		for p in ps:
			(y, x, c) = p
			if c == -1:
				continue
			(dx, dy) = dd[c]
			nx = x + dx
			ny = y + dy
			if U[ny][nx] == -1:
				U[ny][nx] = 1
				if S[ny][nx] == 'X':
					rest -= 1
					p[2] = -1
					qs.append((ny, nx))
				else:
					p[0] = ny
					p[1] = nx
				qs.append((y, x))
		for (y, x) in qs:
			U[y][x] = -1
		t += 1
	if t <= 180:
		print(t)
	else:
		print('NA')


from collections import defaultdict
from typing import Dict

class Players(object):

	def __init__(self):
		self.players: Dict[int, 'Player'] = {}
		self.reservation = defaultdict(list)
		self.square = None
		self.goal = []

	def set_goal(self, x, y):
		self.goal.append((x, y))

	def add(self, player: 'Player'):
		self.players[len(self.players)] = player

	def search_all(self):
		for (i, player) in self.players.items():
			(x, y, d) = player.search(self.square)
			self.reservation[x, y].append(((d - 2) % 4, i))
		for (k, v) in self.reservation.items():
			if len(v) == 1:
				continue
			self.reservation[k] = [min(v)]

	def move_all(self):
		for ((x, y), l) in self.reservation.items():
			_id = l[0][1]
			(_x, _y) = self.players[_id].pos
			self.players[_id].move(x, y)
			(self.square[_y][_x], self.square[y][x]) = ('.', 'o')
		self.reservation.clear()
		for (i, player) in self.players.copy().items():
			(x, y) = player.pos
			if (x, y) in self.goal:
				del self.players[i]
				self.square[y][x] = '.'

	@property
	def is_finished(self):
		return len(self.players) == 0

class Player(object):
	dir_dict = {'E': 0, 'N': 1, 'W': 2, 'S': 3}
	dir_diff = ((1, 0), (0, -1), (-1, 0), (0, 1))

	def __init__(self, x, y, direction):
		self.x = x
		self.y = y
		self.dir = self.dir_dict[direction]

	def search(self, square):
		for i in range(self.dir - 1, self.dir + 3):
			(dx, dy) = self.dir_diff[i % 4]
			if square[self.y + dy][self.x + dx] in ('.', 'X'):
				self.dir = i % 4
				return (self.x + dx, self.y + dy, self.dir)
		else:
			return (self.x, self.y, self.dir)

	def move(self, x, y):
		(self.x, self.y) = (x, y)

	@property
	def pos(self):
		return (self.x, self.y)
while True:
	(W, H) = map(int, input().split())
	if W == 0:
		break
	square = []
	players = Players()
	for y in range(H):
		square.append(list(input()))
		for (x, c) in enumerate(square[-1]):
			if c in 'ENWS':
				players.add(Player(x, y, c))
			elif c == 'X':
				players.set_goal(x, y)
	players.square = square
	for i in range(1, 121):
		players.search_all()
		players.move_all()
		if players.is_finished:
			print(i)
			break
	else:
		print('NA')


from sys import stdin
from itertools import chain
head = [[8, 1, 2, 4], [1, 2, 4, 8], [2, 4, 8, 1], [4, 8, 1, 2]]
while True:
	(W, H) = map(int, stdin.readline().split())
	m = [[0] * W for _ in range(H)]
	ps = []
	if not (W or H):
		break
	flag = True
	for h in range(H):
		s = stdin.readline()
		if 'X' in s:
			flag = False
		for w in range(W):
			if s[w] in ['.', 'X', 'E', 'N', 'W', 'S']:
				m[h][max(0, w - 1)] |= 1
				m[min(H - 1, h + 1)][w] |= 2
				m[h][min(W - 1, w + 1)] |= 4
				m[max(0, h - 1)][w] |= 8
			if s[w] in ['E', 'N', 'W', 'S']:
				ps.append([h, w, ['E', 'N', 'W', 'S'].index(s[w])])
			if s[w] == 'X':
				m[h][w] |= 16
	if W <= 2 or H <= 2:
		print(1)
		continue
	ttt = 0
	while True:
		ttt += 1
		if ttt > 180:
			print('NA')
			break
		mt = [[0] * W for _ in range(H)]
		for p in ps:
			mt[p[0]][p[1]] |= 1
		dest = []
		for (pi, p) in enumerate(ps):
			for i in range(4):
				if head[p[2]][i] & m[p[0]][p[1]]:
					d = head[p[2]][i]
					if d == 1 and (not [p[0], p[1] + 1] in [a[:2] for a in ps]):
						p[2] = 0
						dest.append([pi, 2, p[0], p[1] + 1])
						break
					elif d == 2 and (not [p[0] - 1, p[1]] in [a[:2] for a in ps]):
						p[2] = 1
						dest.append([pi, 3, p[0] - 1, p[1]])
						break
					elif d == 4 and (not [p[0], p[1] - 1] in [a[:2] for a in ps]):
						p[2] = 2
						dest.append([pi, 0, p[0], p[1] - 1])
						break
					elif d == 8 and (not [p[0] + 1, p[1]] in [a[:2] for a in ps]):
						p[2] = 3
						dest.append([pi, 1, p[0] + 1, p[1]])
						break
			else:
				dest.append([pi, p[2] + 2 & 3, p[0], p[1]])
		dest = sorted(dest, key=lambda x: (x[2:], x[1]))
		dellist = []
		for (pi, d, dy, dx) in dest:
			if not mt[dy][dx]:
				mt[dy][dx] |= 1
				ps[pi][:2] = [dy, dx]
			if m[ps[pi][0]][ps[pi][1]] & 16:
				dellist.append(pi)
		for idx in sorted(dellist)[::-1]:
			del ps[idx]
		if not len(ps):
			print(ttt)
			break


while True:
	dic = {'#': -3, '.': -1, 'X': -2, 'E': 0, 'N': 1, 'W': 2, 'S': 3}

	def fix(c):
		return dic[c]
	(w, h) = map(int, input().split())
	if w == 0:
		break
	mp = [list(map(fix, list(input()))) for _ in range(h)]
	persons = []
	for y in range(h):
		for x in range(w):
			if mp[y][x] in (0, 1, 2, 3):
				persons.append([x, y, mp[y][x]])
	vx = (1, 0, -1, 0)
	vy = (0, -1, 0, 1)
	time = 0
	while time < 180:
		if not persons:
			print(time)
			break
		reserve = {}
		for (index, state) in enumerate(persons):
			(x, y, d) = state
			for i in range(d - 1, d + 3):
				(dx, dy) = (vx[i % 4], vy[i % 4])
				if mp[y + dy][x + dx] in (-1, -2):
					persons[index][2] = i % 4
					if (x + dx, y + dy) in reserve:
						if reserve[x + dx, y + dy][1] > (i + 2) % 4:
							reserve[x + dx, y + dy] = (index, (i + 2) % 4, mp[y + dy][x + dx])
					else:
						reserve[x + dx, y + dy] = (index, (i + 2) % 4, mp[y + dy][x + dx])
					break
		reserve = sorted(reserve.items(), key=lambda a: -a[1][0])
		for (k, v) in reserve:
			(nx, ny) = k
			(index, nd, panel) = v
			(px, py, _) = persons[index]
			mp[py][px] = -1
			if panel == -1:
				persons[index] = [nx, ny, (nd + 2) % 4]
				mp[ny][nx] = (nd + 2) % 4
			else:
				persons.pop(index)
		time += 1
	else:
		print('NA')