AT_xmascon19_f.Stamps 1

兔子有一个 $H \times W$ 的矩形格子。格子的第 $i$ 行（$1 \leq i \leq H$）、第 $j$ 列（$1 \leq j \leq W$）的格子称为格子 $(i, j)$。

格子 $(i, j)$ 的初始状态由字符 $S_{i,j}$ 表示，# 表示已经被涂黑，. 表示尚未被涂黑。

兔子收到了一个圣诞礼物——一个印章。

每次使用这个印章，可以将一个高 $H/2$、宽 $W/2$ 的矩形区域全部涂黑。也就是说，选择整数 $i_0, j_0$ 后，可以将所有满足 $i_0 \leq i < i_0 + H/2$ 且 $j_0 \leq j < j_0 + W/2$ 的格子 $(i, j)$ 全部涂黑。

兔子想用这个印章将所有格子都涂黑。请问最少需要盖几次印章？

输入以如下格式从标准输入读入。

$H$ $W$
$S_{1,1} S_{1,2} \ldots S_{1,W}$
$S_{2,1} S_{2,2} \ldots S_{2,W}$
$\vdots$
$S_{H,1} S_{H,2} \ldots S_{H,W}$

输出使所有格子都被涂黑所需的最小印章次数。

限制条件

• $2 \leq H, W \leq 1000$
• $H, W$ 均为偶数
• $S_{i,j}$ 仅为 . 或 #

样例解释 1

例如，如下图所示的盖章方式，可以在 $3$ 次内将所有格子涂黑。

由 ChatGPT 4.1 翻译