보물찾기

질은 플레이어가 보물을 찾아가는 스마트폰 게임을 만들었다. 앱은 GPS로 플레이어의 위치를 파악하고, 그 위치에서 보물로 가는 경로의 다음 방향을 알려 준다. 플레이어가 보물이 놓인 위치에 도착하면 앱이 (가상의) 보물을 준다.

플레이어가 보물을 찾기까지 몇 번 이동하는지 구하라.

첫째 줄에 두 정수 $R$과 $C$가 주어진다 ($1 \le R \le 200$, $1 \le C \le 200$). 각각 게임판의 행 개수와 열 개수다.

다음 $R$개 줄에는 게임판이 주어진다. 각 줄은 정확히 $C$개의 문자로 이루어지고, 문자 하나가 그 칸에서 할 행동을 정한다. 문자는 다섯 가지다. N은 이전 행으로, S는 다음 행으로, W는 이전 열로, E는 다음 열로 이동한다는 뜻이고, T는 보물이 놓인 위치다. 보물이 있는 칸은 정확히 하나다.

플레이어는 첫째 행 첫째 열에서 시작해, 서 있는 칸에 적힌 방향을 따라 이동한다.

방향을 따라가다 보물에 도착하면 이동 횟수를 한 줄에 출력한다. 방향을 따라가다 게임판 밖으로 나가면 Out을 한 줄에 출력한다. 게임판 안에 계속 머물지만 보물에 끝내 도착하지 못하면 Lost를 한 줄에 출력한다.