Bessie è di nuovo bloccata dal lato sbagliato del fienile di Farmer John. Vede male e necessita aiuto per attraversarlo.

Il fienile è una griglia $N \times N$ di celle quadrate ($2 \leq N \leq 20$), vuote o con fieno invalicabile. Parte da basso a sinistra $(1,1)$ verso alto a destra $N,N$. I comandi sono «avanti», «gira 90 gradi a sinistra», «a destra». Cerca la sequenza più corta. Se tenta di uscire, nel muro, o entrare nel fieno, resta ferma e passa al comando successivo.

Non sa se all’inizio guarda in alto verso $(1,2)$ o a destra verso $(2,1)$. La sequenza più corta deve funzionare in entrambi i casi. Arrivata ignora altri comandi.

Input

Leggi dall’input standard.

La prima riga contiene $N$.

Le successive $N$ hanno esattamente $N$ caratteri. Il primo dell’ultima è $(1,1)$, l’ultimo della prima è $(N,N)$.

H indica fieno, E una cella vuota.

$(1,1)$ e $N,N$ sono vuote ed esiste un percorso di celle vuote da $(1,1)$ a $N, N$.

Output

Scrivi sull’output standard.

Stampa una riga con la lunghezza della sequenza più corta che arriva, orientata all’inizio in alto o a destra.

Esempi

Input 1

3
EHE
EEE
EEE

Output 1

9

Nota

«Avanti, destra, avanti, avanti, sinistra, avanti, sinistra, avanti, avanti» funziona in entrambi i casi dell’esempio.

Autore del problema: Brian Dean