Є місто, розділене на сітку клітинок із \(H\) рядів та \(W\) стовпців. Комірка в \(i\)-му рядку та \(j\)-му стовпці є вільною для проходу, якщо \(S_{i,j}\) є '.' і заблокована, якщо \(S_{i,j}\) є #. Степан піде з дому на рибний ринок. Його дім знаходиться в клітині у верхньому лівому куті, а рибний ринок — у клітині в нижньому правому куті. Степан може перемістити на одну клітинку вгору, вниз, вліво або вправо до вільної клітини. Він не може покидати місто. Він також не може зайти в блоковану клітину. Однак його фізична сила дозволяє йому знищити всі блоки в квадратній області розміром \(2 \times 2\) за його вибором одним ударом, роблячи ці клітини вільними і прохідними.

Знайдіть мінімальну кількість ударів, необхідну Степану, щоб дістатися до рибного ринку.

Формат вхідних даних

Перший рядок містить цілі числа \(H,W\) (\(2 \le H,W \le 500\))

Наступні  \(H\) рядків містять по \(W\) символів \(S_{i,j}\) (\(S_{i,j}\)='.','#')

Формат вихідних даних

У вихідний потік виведіть шукану кількість ударів.

Примітка

До прикладу 1:

Він може дістатися до рибного ринку, наприклад, знищивши блоки в квадраті 2×2 з клітинками, які позначені * нижче.

..#..
#.**#
##**#
#.#.#
..#..

Приклад вхідних даних

5 5
..#..
#.#.#
##.##
#.#.#
..#..

Приклад вихідних даних

1

Приклад вхідних даних

5 7
.......
######.
.......
.######
.......

Приклад вихідних даних

0

Приклад вхідних даних

8 8
.#######
########
########
########
########
########
########
#######.

Приклад вихідних даних

5