题目描述

有一座城市被划分为 $H$ 行 $W$ 列的格子状区块。从上往下第 $i$ 行，从左往右第 $j$ 列的区块，若 $S_{i,j}$ 为 .，则表示道路；若为 #，则表示围墙。

高桥君打算从自己家出发去鱼店买东西。高桥君的家在城市的左上角区块，鱼店在城市的右下角区块。

高桥君可以从当前所在的区块移动到上下左右相邻的道路区块。不能走出城市外部，也不能移动到围墙区块。不过，高桥君力大无穷，可以每次用一拳将任意 $2\times 2$ 的区块内的围墙全部打碎变成道路。

请你求出高桥君到达鱼店至少需要出拳多少次。

输入格式

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

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

输出格式

请输出答案。

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

1

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

0

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

5

说明/提示

限制条件

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

样例解释 1

例如，如果破坏用 * 表示的 $2\times 2$ 区块内的围墙，就能到达鱼店。

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

被破坏的 $2\times 2$ 区块不要求全部为围墙。

样例解释 2

虽然需要绕远路，但无需破坏任何围墙也能到达鱼店。