문제

민재는 알고리즘 동아리방에서 길 찾기 로봇을 조종하고 있다. 로봇은 $N \times N$ 크기의 격자판 모양인 동아리방 안에서 움직인다. ($2 \le N \le 20$)

격자의 각 칸은 비어 있거나 장애물로 막혀 있다. 로봇은 왼쪽 아래 구석인 $(1, 1)$에서 출발하여 오른쪽 위 구석인 $(N, N)$에 도착해야 한다. 민재는 로봇에게 다음과 같은 세 가지 명령 중 하나를 담은 수열을 전송할 수 있다.

• 직진: 현재 바라보는 방향으로 한 칸 전진한다.
• 왼쪽 회전: 제자리에서 왼쪽으로 90도 회전한다.
• 오른쪽 회전: 제자리에서 오른쪽으로 90도 회전한다.

로봇이 격자 밖으로 나가려고 하거나 장애물이 있는 칸으로 이동하려고 하면, 로봇은 움직이지 않고 수열의 다음 명령을 수행한다. 단, 로봇이 한 번 목표 지점인 $(N, N)$에 도달하면 그 이후의 명령은 모두 무시하고 그 자리에 멈춘다.

안타깝게도 민재는 로봇이 처음에 위쪽($(1, 2)$ 방향)을 향하고 있는지, 아니면 오른쪽($(2, 1)$ 방향)을 향하고 있는지 알지 못한다. 민재는 로봇이 처음에 어느 방향을 향하고 있었더라도 상관없이 목표 지점에 무사히 도달하게 할 수 있는 가장 짧은 명령어 수열을 만들고자 한다. 민재가 만들어야 하는 최단 명령어 수열의 길이를 구하시오.

입력

첫째 줄에 $N$이 주어진다. ($2 \le N \le 20$)

다음 $N$개의 줄에는 격자의 상태를 나타내는 $N$글자의 문자열이 주어진다. 입력의 마지막 줄의 첫 번째 문자가 $(1, 1)$ 칸의 상태를 나타내며, 입력의 첫 번째 줄의 마지막 문자가 $(N, N)$ 칸의 상태를 나타낸다.

각 문자는 빈 공간을 나타내는 E 또는 장애물을 나타내는 H 중 하나이다.

$(1, 1)$과 $(N, N)$ 칸은 항상 E이며, 빈 공간만을 이용하여 $(1, 1)$에서 $(N, N)$까지 이동할 수 있는 경로가 항상 존재함이 보장된다.

출력

로봇이 처음에 위쪽 또는 오른쪽 중 어느 방향을 향하고 있었더라도 목표 지점에 도달하게 하는 가장 짧은 명령어 수열의 길이를 출력한다.

예제 입력 1

3
EHE
EEE
EEE

예제 출력 1

9