В средней полосе России иногда растет лес. Для того, чтобы отделить лес от полезных пахотных земель, между лесом и полем был построен забор. Однако лес со временем растет и забор требуется перенести.

Местность можно представить в виде карты из n × m клеток. Каждая клетка содержит в себе либо лес, либо поле, либо забор. Клетки содержащие забор обладают следующими свойствами:

1. Забор связен. Это значит, что от каждой его клетки до каждой можно дойти, передвигаясь только по соседним клеткам (соседними считаются клетки, имеющие общую сторону).
2. Забор минимален по включению, то есть убрав какую-либо клетку из забора (заменив её на лес или поле), он перестанет быть забором.
3. Забор разделяет лес и поле, а именно все клетки слева от забора являются лесом, все клетки справа от забора являются полем.
4. Забор можно представить в виде последовательности клеток таким образом, что следующая клетка находится от предыдущей слева, справа или снизу.

Вам разрешается под забор использовать все клетки, которые он занимал изначально, а также клетки, находящиеся не более чем на один справа от исходных клеток забора (запрещается использовать левый и правый столбцы карты). Вашей задачей будет построить забор минимальной длины, удовлетворяющий всем вышеприведенным условиям забора. Известно, что изначальный забор является забором, а также, что левый столбец карты целиком занят лесом, а правый столбец карты целиком занят полем.

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

В первой строке находятся два числа n и m (1 ≤ n, m ≤ 1000) - размеры карты. Далее следует n строк по m символов в каждой - карта, описывающая исходное положение леса, поля и забора. Клетки, занятые лесом, обозначаются символом "F", клетки, занятые полем - символом ".", клетки, занятые забором - символом "#".

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

Выведите минимальную длину забора, которую можно получить.