На тренировочном полигоне есть прямоугольная схема из n рядов и m колонок. Каждая позиция схемы обозначает участок полигона и задаётся одним из символов:

• . — свободный участок коридора;
• # — стена;
• S — стартовая позиция бойца;
• F — контрольная точка, до которой нужно добраться.

За один ход можно перейти из текущего участка в соседний по стороне свободный участок. Проходить через стены нельзя.

Требуется определить минимальное количество ходов, необходимое, чтобы добраться от S до F. Если сделать это невозможно, выведите -1.

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

В первой строке даны два целых числа n и m.

В следующих n строках записано по строке длины m, описывающей схему полигона.

Гарантируется, что на схеме ровно одна позиция S и ровно одна позиция F.

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

Выведите минимальное количество ходов от S до F, либо -1, если путь отсутствует.

Ограничения

• 1 <= n, m <= 1000
• n * m <= 200000

Примеры

Пример 1

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

1 2
SF

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

1

Пример 2

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

3 3
F.#
.S.
#.#

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

2