Problem Statement

We have a grid with $N$ rows and $M$ columns, where each square is painted black or white. Here, at least one square is painted black. The initial state of the grid is given as $N$ strings $S_1,S_2,\ldots,S_N$ of length $M$. The square at the $i$-th row from the top and $j$-th column from the left is painted black if the $j$-th character of $S_i$ is #, and white if it is ..

Takahashi wants to repaint some white squares (possibly zero) black so that the squares painted black are connected. Find the minimum number of squares he needs to repaint to achieve his objective.

Here, the squares painted black are said to be connected when, for every pair of squares $(S,T)$ painted black, there are a positive integer $K$ and a sequence of $K$ squares $X=(x_1,x_2,\ldots,x_K)$ painted black such that $x_1=S$, $x_K=T$, and $x_i$ and $x_{i+1}$ share a side for every $1\leq i\leq K-1$. It can be proved that, under the constraints of the problem, there is always a way for Takahashi to achieve his objective.

Constraints

• $1 \leq N \leq 100$
• $1\leq M \leq 7$
• $N$ and $M$ are integers.
• $S_i$ is a string of length $M$ consisting of # and ..
• The given grid has at least one square painted black.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the minimum number of squares that Takahashi needs to repaint for the squares painted black to be connected.