Falling Figure — Min Obstacles to Remove

In the grid, * forms a non-empty 4-connected shape, # is an obstacle, and - is an empty cell. The shape does not rotate or deform; it only moves down as a whole, one cell at a time, until at least one of its cells reaches the bottom row. Find the minimum number of distinct obstacles that must be removed. The original site's example does not satisfy the connectivity constraint, so this site wrote a new example that follows the rules.

输入格式

The first line contains the number of rows R and the number of columns C (1..100); the next R lines are strings of length C containing only *, #, and -. The shape is guaranteed to be non-empty and 4-connected.

输出格式

Output the answer as described; separate multiple results with spaces in order, and output an empty line for an empty array.

样例 1

输入：

3 2
**
-#
--

输出：

1

样例 2

输入：

1 1
*

输出：

0

样例 3

输入：

3 3
***
###
###

输出：

6

样例说明

Example 1: the shape moves down two rows, and the upper-right asterisk must pass through the obstacle on the right; after removing that one obstacle, both asterisks can reach the bottom row, so the answer is 1.