로빈슨

폭풍에 휩쓸려 무인도에 떠밀려 온 로빈슨은 바다로 나가 사람이 사는 곳을 찾기 위해 배를 만들었다. 그는 노련한 뱃사람이라 배를 제대로 만들었다. 배에는 세로 방향의 대칭축이 있고, 뱃머리는 좁으며 가운데로 갈수록 점점 넓어졌다가 다시 배꼬리로 갈수록 좁아진다. 특히 가운데 어딘가에서는 뱃머리나 배꼬리보다 폭이 더 넓다.

그런데 로빈슨은 아주 나쁜 곳에 배를 띄웠다. 배 주위는 매우 빽빽하고 단단한 갈대로 둘러싸여 있어 배로는 뚫고 나갈 수 없다. 그래도 갈대 사이를 조심스럽게 헤쳐 나가면 넓은 바다에 도달할 수 있을지도 모른다.

배는 방향을 바꾸는 능력이 없다. 앞으로, 뒤로, 그리고 옆으로(왼쪽이나 오른쪽으로) 움직일 수는 있지만 회전할 수는 없다. 따라서 필요하다면 뱃머리가 아니라 배꼬리나 옆면을 앞세운 채로 움직여도 된다.

로빈슨이 넓은 바다에 도달할 수 있는지 판단하여라.

문제를 단순하게 하기 위해, 섬과 그 주변을 정사각형 단위 칸으로 나눈 정사각형 지도로 나타낸다. 각 칸에는 물, 로빈슨 배의 일부, 또는 장애물(땅이나 갈대) 중 하나가 들어 있다. 처음에 배는 동서남북 중 한 방향과 나란히 놓여 있다. 즉 세로 대칭축이 그 방향과 평행하며, 배가 덮고 있는 칸들의 중심을 지난다.

넓은 바다는 지도가 끝나는 곳에서 시작한다고 본다. 따라서 배가 지도로 표시된 영역을 완전히 벗어나면 로빈슨은 넓은 바다에 도달한 것이다. 한 번의 이동은 배를 고른 방향(북, 남, 동, 서)으로 한 칸 옮기는 것이다. 이동 전과 후 모두 배가 완전히 물 위에 있을 때에만, 즉 장애물이 있는 칸을 절대 덮지 않을 때에만 그 이동이 허용된다. 지도 밖의 칸은 넓은 바다(물)로 취급한다.

표준 입력으로 지도를 읽어, 배가 지도로 표시된 영역을 완전히 벗어나는 데 필요한 최소 이동 횟수를 계산하여 출력하는 프로그램을 작성하여라.

첫째 줄에 지도 한 변의 길이인 정수 $n$ ($3 \le n \le 2000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 지도 한 행의 칸들을 나타내는 $n$개의 문자가 주어진다. 각 문자는 다음 중 하나이다.

• . — 물이 있는 칸
• X — 장애물(땅이나 갈대)이 있는 칸
• r — 로빈슨 배의 일부가 있는 칸

배가 지도로 표시된 영역을 완전히 벗어나는 데 필요한 최소 이동 횟수를 한 줄에 출력한다. 배가 넓은 바다에 도달하는 것이 불가능하다면, 대신 NIE라는 단어를 출력한다.