Problem Description

The rabbit has a rectangular grid of size $H \times W$. The cell in the $ i $-th row (from the top) ($1 \le i \le H$) and the $ j $-th column (from the left) ($1 \le j \le W$) is referred to as cell $ (i,j) $.

The initial state of cell $ (i,j) $ is represented by the character $ S_{i,j} $, where # indicates that the cell is painted black, and . indicates that it is not painted.

The rabbit received a stamp as a Christmas present.

When this stamp is pressed once, it can paint a rectangle of size $H/2 \times W/2$ black. That is, by choosing integers $ i_0, j_0 $, all cells $ (i,j) $ such that $i_0 \le i < i_0 + H/2$ and $j_0 \le j < j_0 + W/2$ can be painted black.

The rabbit wants to use this stamp to paint all cells black. What is the minimum number of times the stamp needs to be pressed?

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ S_{1,1} $$ S_{1,2} $$ ... $$ S_{1,W} $ $ S_{2,1} $$ S_{2,2} $$ ... $$ S_{2,W} $ $ : $ $ S_{H,1} $$ S_{H,2} $$ ... $$ S_{H,W} $

Output Format

Output the minimum number of times the stamp needs to be pressed to paint all cells black.

Sample Input and Output

Sample Input #1

4 4
#..#
#.#.
..##
..##

Sample Output #1

3

Sample Input #2

2 6
######
######

Sample Output #2

0

Notes/Hints

Constraints

• $2 \le H,W \le 1000$
• Both $ H $ and $ W $ are even numbers
• $ S_{i,j} $ is either . or #

Sample Explanation 1

For example, pressing the stamp as shown in the figure below allows all cells to be painted black in 3 presses.

见题面 Input 部分

见题面 Output 部分