Bessie quedó de nuevo al lado equivocado del granero de Farmer John. Ve mal y necesita ayuda para cruzarlo.

Es una cuadrícula $N \times N$ de celdas cuadradas ($2 \leq N \leq 20$), vacías o con heno infranqueable. Parte de abajo a la izquierda $(1,1)$ hacia arriba a la derecha $N,N$. Puedes ordenar «avanzar», «girar 90 grados a izquierda» o «a derecha». Busca la secuencia más corta. Si intenta salir, chocar con la pared o entrar al heno, no se mueve y pasa a la siguiente orden.

No sabe si mira arriba hacia $(1,2)$ o a la derecha hacia $(2,1)$. Da la secuencia más corta que sirva en ambos casos. Al llegar ignora órdenes posteriores.

Entrada

Lee de la entrada estándar.

La primera línea contiene $N$.

Las siguientes $N$ tienen exactamente $N$ caracteres. El primero de la última es $(1,1)$; el último de la primera es $(N,N)$.

H representa heno, E una celda vacía.

$(1,1)$ y $N,N$ están vacías y hay un camino de celdas vacías desde $(1,1)$ hasta $N, N$.

Salida

Escribe en la salida estándar.

Imprime una línea con la longitud de la secuencia más corta que llegue, mire inicialmente arriba o a la derecha.

Ejemplos

Entrada 1

3
EHE
EEE
EEE

Salida 1

9

Nota

«Avanzar, derecha, avanzar, avanzar, izquierda, avanzar, izquierda, avanzar, avanzar» funciona para ambas orientaciones del ejemplo.

Autor del problema: Brian Dean