Bessie znowu utknęła po złej stronie stodoły Farmer John. Ma słaby wzrok i potrzebuje pomocy w przejściu.

Stodoła to siatka $N \times N$ kwadratowych pól ($2 \leq N \leq 20$), pustych lub z nieprzekraczalnym sianem. Idzie z dołu po lewej $(1,1)$ do góry po prawej $N,N$. Polecenia: „naprzód”, „90 stopni w lewo”, „90 stopni w prawo”. Szukasz najkrótszej sekwencji. Gdy próbuje wyjść, w ścianę, lub wejść w siano, nie rusza się i przechodzi do następnego polecenia.

Nie wie, czy patrzy początkowo w górę do $(1,2)$ czy w prawo do $(2,1)$. Najkrótsza sekwencja ma działać dla obu. Po dotarciu ignoruje dalsze polecenia.

Wejście

Czytaj ze standardowego wejścia.

Pierwszy wiersz zawiera $N$.

Następne $N$ ma po dokładnie $N$ znaków. Pierwszy ostatniego to $(1,1)$, ostatni pierwszego $(N,N)$.

H oznacza siano, E puste pole.

$(1,1)$ i $N,N$ są puste, istnieje ścieżka pustych pól od $(1,1)$ do $N, N$.

Wyjście

Pisz na standardowe wyjście.

Wypisz wiersz z długością najkrótszej sekwencji docierającej przy obu początkowych kierunkach.

Przykład

Wejście 1

3
EHE
EEE
EEE

Wyjście 1

9

Uwagi

„Naprzód, prawo, naprzód, naprzód, lewo, naprzód, lewo, naprzód, naprzód” działa w obu kierunkach przykładu.

Autor zadania: Brian Dean