Коров'яча навігація

Амбар представлений у вигляді сітки розміром n на n символів, деякі з яких є порожніми, а інші зайнятими. Бессі починає свій шлях з лівого нижнього кута (1, 1) і повинна дістатися до правого верхнього кута (n, n). Ви можете керувати її рухом за допомогою набору команд: "вперед", "повернись ліворуч на 90 градусів", "повернись праворуч на 90 градусів". Ваше завдання — скласти найкоротшу послідовність команд, яка приведе її до мети. Якщо виконання якоїсь команди неможливе, Бессі просто ігнорує її і переходить до наступної.

Проблема в тому, що Бессі не знає, в якому напрямку вона дивиться на початку: чи то на клітинку (1, 2), чи на клітинку (2, 1). Вам потрібно скласти таку послідовність команд, яка приведе її до мети найкоротшим шляхом, незалежно від початкового напрямку. Як тільки Бессі досягає мети, вона ігнорує всі подальші команди.

Вхідні дані

Перший рядок містить число n (2 ≤ n ≤ 20). Кожен з наступних n рядків містить рівно n символів, що описують амбар. Перший символ останнього рядка відповідає клітинці (1, 1), а останній символ першого рядка — клітинці (n, n).

Кожен символ може бути або H (непрохідний стіг сіна), або E (порожня клітинка).

Гарантується, що клітинки 1, 1 і n, n є порожніми, і існує шлях по порожніх клітинках з 1, 1 до n, n.

Вихідні дані

Виведіть довжину найкоротшої послідовності команд, яка приведе Бессі до мети, незалежно від її початкового напрямку (вгору або вправо).

Приклади

Примітка

У цьому прикладі послідовність команд "Вперед, Праворуч, Вперед, Вперед, Ліворуч, Вперед, Ліворуч, Вперед, Вперед" приведе Бессі до мети незалежно від її початкової орієнтації.