Здание представлено прямоугольной таблицей размера n x m.

Каждая клетка таблицы имеет один из следующих типов:

• # — перегородка, пройти через неё нельзя;
• . — свободное помещение;
• S — место, где в момент времени 0 находится человек;
• F — очаг огня.

Каждую минуту одновременно происходят два процесса:

• человек может перейти в соседнюю по стороне клетку, если она не является перегородкой;
• огонь распространяется во все соседние по стороне клетки, которые не являются перегородками.

Человек не может находиться в клетке в тот момент, когда огонь уже находится там, или приходит туда в эту же минуту.

Нужно определить минимальное количество минут, за которое человек сможет оказаться в любой граничной клетке здания и при этом остаться в безопасности.

Если человек изначально находится в граничной клетке и огонь не находится там в момент 0, ответ равен 0.

Если безопасно добраться до границы невозможно, выведите -1.

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

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

Далее следуют n строк длины m, описывающие план здания. Каждая строка состоит только из символов ., #, S и F.

Гарантируется, что в таблице ровно одна клетка S. Очагов огня может быть любое количество, в том числе ни одного.

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

Выведите одно целое число — минимальное количество минут, необходимое для безопасного попадания в граничную клетку, либо -1, если это невозможно.

Ограничения

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

Примеры

Пример 1

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

1 1
S

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

0

Пример 2

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

3 3
#.#
.S.
#.#

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

1