题目描述

有一个由 $H$ 行 $W$ 列的网格单元格组成的城镇。如果第 $i$ 行从上往下数第 $j$ 列从左往右数的单元格是可通过的则记为 $S_{i,j}$ 是.，否则记为#。

Takahashi 将从他的房子前往鱼市。他的房子位于左上角的单元格中，鱼市位于右下角的单元格中。

Takahashi 可以向上、向下、向左或向右移动到可通过的单元格。他不能离开城镇。他也不能进入障碍单元格。然而，他的体力允许他用一拳摧毁一个 $2 \times 2$ 的选定方块区域内的所有障碍单元格，使这些单元格变为可通过。

请找出 Takahashi 到达鱼市所需要的最小拳击次数。

约束条件

• $2 \leq H,W \leq 500$
• $H$ 和 $W$ 均为整数。
• $S_{i,j}$ 可以是.或#。
• $S_{1,1}$ 和 $S_{H,W}$ 均为.。

输入

输入采用以下格式从标准输入给出：

$H$ $W$ $S_{1,1} \ldots S_{1,W}$ $\vdots$ $S_{H,1} \ldots S_{H,W}$

输出

打印答案。

示例输入 1

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

示例输出 1

1

例如，他可以通过摧毁下图所示的标记为*的 $2 \times 2$ 方块区域内的障碍单元格到达鱼市。

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

并不要求区域内的所有 $2 \times 2$ 单元格都是障碍单元格。

示例输入 2

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

示例输出 2

0

尽管他需要绕一大圈走，但他可以到达鱼市而无需摧毁障碍物单元格。

示例输入 3

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

示例输出 3

5