Амбар описывается решёткой 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.

Выходные данные

Выведите длину кратчайшей последовательности команд, которая приведёт Бесси к цели, вне зависимости куда она смотри вначале, вверх или вправо.

Пояснение

В этом примере Инструкции "Вперёд, Вправо, Вперёд, Вперёд, Влево, Вперёд, Влево, Вперёд, Вперёд" приведут Бесси к назначению вне зависимости от начальной ориентации.