Bessie는 또 Farmer John 헛간의 잘못된 쪽에 갇혔다. 시력이 나빠 건너가는 데 도움이 필요하다.

헛간은 정사각형 칸 $N \times N$의 격자 ($2 \leq N \leq 20$)이며 빈 칸 또는 통과 못할 건초가 있다. 왼쪽 아래 $(1,1)$에서 오른쪽 위 $N,N$로 간다. 명령은 “전진”, “왼쪽으로 90도 회전”, “오른쪽으로 90도 회전”이다. 가장 짧은 명령열을 원한다. 격자 밖 벽이나 건초로 가려 하면 이동하지 않고 다음 명령으로 넘어간다.

처음 위 $(1,2)$ 또는 오른쪽 $(2,1)$을 보는지 모른다. 둘 다 도착하게 할 가장 짧은 명령열을 주어라. 도착 후 남은 명령은 무시한다.

입력

표준 입력에서 읽는다.

첫 줄에 $N$.

다음 $N$줄은 정확히 $N$개 문자이다. 마지막 줄 첫 문자가 $(1,1)$, 첫 줄 마지막이 $(N,N)$이다.

H는 건초, E는 빈 칸이다.

$(1,1)$과 $N,N$은 비어 있고 $(1,1)$에서 $N, N$까지 빈 칸 경로가 보장된다.

출력

표준 출력에 쓴다.

처음 위나 오른쪽 어느 쪽을 봐도 도착하는 가장 짧은 명령열 길이를 한 줄에 출력한다.

예제

입력 1

3
EHE
EEE
EEE

출력 1

9

참고

“전진, 오른쪽, 전진, 전진, 왼쪽, 전진, 왼쪽, 전진, 전진”은 예제 두 방향 모두 도착한다.

문제 작성자: Brian Dean