Description

小黄要和小杨爆了！小杨藏在一个迷宫里，这个迷宫是由字符 #. 组成的 $n$ 行 $m$ 列的矩形，其中 # 表示墙体，. 表示迷宫中的通道。迷宫的通道部分可以不连续。

小黄可以在迷宫的通道位置设置一种冲击波发射器，当发射器激活时，可以向预定的方向（上下左右四个方向之一）发射冲击波。冲击波可以在通道中沿发射方向延伸，直到碰到墙体终止，这个方向上从冲击波发射器开始所有连续的迷宫通道都是冲击波的影响范围，包括设置发射器的那个通道位置。冲击波发射器和由发射器发射的冲击波都不会影响其他冲击波的延伸。一个迷宫的通道部分可以设置多个冲击波发射器。小黄虽然不知道小杨在迷宫中的具体位置，但只要小黄在迷宫中设置多个冲击波发射器，同时发射冲击波，使得迷宫通道能被冲击波的范围完全覆盖，那么小杨必似无疑。

请你帮助小黄完成这个邪恶计划。由于小黄欠缺经费，请你告诉小黄至少需要多少个冲击波发射器能够保证迷宫通道被冲击波范围完全覆盖。

Format

Input

第一行有两个整数 $m, n\ (1 \leq m, n \leq 500)$，表示迷宫的行数和列数。

接下来 $m$ 行，每行一个长度为 $n$ 的字符串。字符串仅包含 #.，分别表示迷宫的墙体和通道。

Output

输出一个整数，表示能够保证迷宫通道被冲击波范围完全覆盖的最少冲击波发射器个数。

Samples

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

5

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

13

Limitation

1s, 1024KiB for each test case.