Робот-уборщик находится в прямоугольной комнате размера n x m, разбитой на клетки. Каждая клетка комнаты имеет один из двух типов:

• . — свободная клетка, по которой робот может проехать;
• # — препятствие, через которое робот проехать не может.

Робот начинает движение в верхнем левом углу комнаты, в клетке (1, 1), и должен добраться до нижнего правого угла, в клетку (n, m).

За один шаг робот может перейти в соседнюю по стороне клетку: вверх, вниз, влево или вправо. Выходить за границы комнаты нельзя, заезжать на клетки с препятствиями тоже нельзя.

Требуется определить минимальное количество шагов, необходимое роботу, чтобы добраться до цели. Если попасть в клетку (n, m) невозможно, выведите -1.

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

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

В следующих n строках задана карта комнаты: каждая строка состоит ровно из m символов . и #.

Гарантируется, что клетки (1, 1) и (n, m) свободны.

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

Выведите одно целое число — минимальное количество шагов, за которое робот может добраться из клетки (1, 1) в клетку (n, m), либо -1, если такого пути не существует.

Ограничения

• 1 <= n, m <= 1000

Примеры

Пример 1

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

1 1
.

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

0

Пример 2

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

2 2
..
..

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

2