有一个城市，被分成了 $H$ 行 $W$ 列的格子状的区域。如果第 $i$ 行，第 $j$ 列的区域 $S_{i,j}$ 是 .，那么就是道路，如果是 #，那么就是墙。

高桥君想从自己的家去鱼店买东西。高桥君的家在城市的左上角的区域，鱼店在城市的右下角的区域。

高桥君可以从自己所在的区域移动到上下左右相邻的道路区域。他不能离开城市。 他不能移动到墙的区域，但是高桥君非常有力量，所以他可以用一次拳头打碎任意一个 $2\times\ 2$ 的区域内的墙，把它们变成道路。

请问高桥君要到达鱼店，至少要打碎多少次墙？

输入按以下格式从标准输入给出。

H W
S_{1,1} ... S_{1,W}
:
S_{H,1} ... S_{H,W}

• $2\ \leq\ H,W\ \leq\ 500$
• $H,W$ 是整数
• $S_{i,j}$ 是 . 或者 #
• $S_{1,1}$ 是 .
• $S_{H,W}$ 是 .

答えを出力せよ。

Sample Explanation 1

例えば、以下の * で表す $2\times\ 2$ の区画にある塀を破壊すると魚屋にたどり着くことができます。 `

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

破壊対象の $2\ \times\ 2$ の区画の全てが塀である必要はありません。

Sample Explanation 2

遠回りが必要ですが、塀を破壊することなく魚屋にたどり着くことができます。