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