Bessie está novamente presa do lado errado do celeiro de Farmer John. Vê mal e precisa de ajuda para atravessá-lo.

O celeiro é uma grelha $N \times N$ de células quadradas ($2 \leq N \leq 20$), vazias ou com feno intransponível. Parte do canto inferior esquerdo $(1,1)$ para o superior direito $N,N$. Comandos: «avançar», «rodar 90 graus à esquerda» ou «à direita». Procure a sequência mais curta. Se tentar sair, para a parede, ou entrar em feno, não se move e passa ao comando seguinte.

Não sabe se olha para cima, $(1,2)$, ou para a direita, $(2,1)$. Dê a sequência mais curta que resulte em ambos os casos. Ao chegar, ignora os seguintes.

Entrada

Leia da entrada padrão.

A primeira linha contém $N$.

As $N$ seguintes têm exatamente $N$ carateres descrevendo o celeiro. O primeiro da última é $(1,1)$, o último da primeira é $(N,N)$.

H indica feno, E célula vazia.

$(1,1)$ e $N,N$ são vazias; há um caminho vazio de $(1,1)$ a $N, N$.

Saída

Escreva na saída padrão.

Imprima uma linha com o comprimento da menor sequência que chega, inicialmente voltada para cima ou à direita.

Exemplos

Entrada 1

3
EHE
EEE
EEE

Saída 1

9

Nota

«Avançar, direita, avançar, avançar, esquerda, avançar, esquerda, avançar, avançar» resulta em ambas as orientações do exemplo.

Autor do problema: Brian Dean