我们都喜欢宝藏,对吗?这就是年轻的瓦夏前往金银岛的原因。
金银岛可以表示为一张被海洋包围的矩形桌子 $$$n \times m$$$。让我们从上到下对字段中具有从 $$$1$$$ 到 $$$n$$$ 的连续整数的行进行编号,并从左到右对具有从 $$$1$$$ 到 $$$m$$$ 的连续整数的列进行编号。将 $$$r$$$ 行和 $$$c$$$ 列中的单元格表示为 $$$(r, c)$$$。一些岛屿单元包含无法通行的森林,而一些单元是免费且可通行的。宝藏隐藏在单元格$$$(n, m)$$$中。
Vasya 在 $$$(1, 1)$$$ 牢房下船。现在他想要到达宝藏。他速度很快,所以他只能从单元格移动到下一行(向下)或下一列(向右)的单元格,即从单元格 $$$(x, y)$$$ 他只能移动到单元格 $$$(x+1, y)$$$ 和 $$$(x, y+1)$$$。当然,瓦夏无法穿过森林无法通行的牢房。
邪恶女巫知道了瓦西亚的旅程,她将阻止他到达宝藏。在瓦西亚采取第一步行动之前,她能够使用她的邪恶魔法在以前空闲的牢房中生长不可通行的森林。女巫能够在任意数量的任意单元格中种植森林,除了 Vasya 下船的单元格 $$$(1, 1)$$$ 和隐藏宝藏的单元格 $$$(n, m)$$$ 之外。
帮助邪恶女巫找出她必须将多少格子变成无法通行的森林,以便瓦夏不再能够到达宝藏。
输入
输入的第一行包含两个正整数 $$$n$$$、$$$m$$$ ($$$3 \le n \cdot m \le 1\,000\,000$$$),即岛屿的大小。
以下 $$$n$$$ 行包含描述岛屿的长度为 $$$m$$$ 的字符串 $$$s_i$$$,如果单元格 $$$(i, j)$$$ 包含不可通行的森林和“.”,则字符串 $$$s_i$$$ 的第 $$$j$$$ 个字符等于“#”。如果小区空闲并且可以通过。让我们提醒您,Vasya 在单元格 $$$(1, 1)$$$ 下船,即第一行的第一个单元格,他想要到达单元格 $$$(n, m)$$$,即最后一行的最后一个单元格。
可以保证单元格 $$$(1, 1)$$$ 和 $$$(n, m)$$$ 为空。
输出
打印唯一的整数$$$k$$$,这是邪恶女巫为了阻止Vasya到达宝藏而必须变成无法通行的森林的最小单元格数量。
示例
输入 #1
2 2 .. ..
输出 #1
2
输入 #2
4 4 .... #.#. .... .#..
输出 #2
1
输入 #3
3 4 .... .##. ....
输出 #3
2
注意
下图展示了第三个示例中的岛屿。蓝色箭头显示 Vasya 可能使用的从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 的可能路径。红色表示女巫可能将一组单元变成无法通行的森林,从而使 Vasya 从 $$$(1, 1)$$$ 到 $$$(n, m)$$$ 的旅程变得不可能。