AT_xmascon19_h.Stamps 3

兔子拥有一个大小为 $H \times W$ 的矩形网格。在这里，第 $i$ 行（$1 \le i \le H$）和第 $j$ 列（$1 \le j \le W$）的格子被称为格子 $(i, j)$。

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

今年，兔子收到了一个圣诞礼物——一套特殊的印章套装。

这套印章包含高达 $10^{10}$ 种不同种类。使用第 $k$ 个印章（$1 \le k \le 10^{10}$）时，它可以一次性涂黑每隔 $p_k$ 格的一系列水平方向连续的格子。这里，$p_k$ 是第 $k$ 小的奇数素数。这意味着，当使用第 $k$ 个印章时，可以任选一个行 $i$ 和一个起始列 $j_0$，将所有满足 $j = j_0 + a \cdot p_k$ 的整数 $a$ 所对应的格子 $(i, j)$ 涂黑。

兔子的目标是将整个网格中的所有格子都涂黑。请你计算出至少需要按多少次印章才能完成这一任务。

输入数据以如下格式给出：

$ H $ $ W $
第一行网格状态：$ S_{1,1} $$ S_{1,2} $$ ... $$ S_{1,W} $第二行网格状态：$ S_{2,1} $$ S_{2,2} $$ ... $$ S_{2,W} $
:
第 $H$ 行网格状态：$ S_{H,1} $$ S_{H,2} $$ ... $$ S_{H,W} $

输出要将所有格子涂黑所需的最少印章次数。

约束

• $1 \le H, W \le 10^5$
• $S_{i,j}$ 要么是 .，要么是 #

示例解释

一个有效的操作示例：

• 使用第 1 个印章（$p_1 = 3$），选定 $i = 1$, $j_0 = 3$。
• 使用第 2 个印章（$p_2 = 5$），选定 $i = 1$, $j_0 = 1$。
• 使用第 4 个印章（$p_4 = 11$），选定 $i = 2$, $j_0 = 0$。
• 又一次使用第 4 个印章（$p_4 = 11$），选定 $i = 2$, $j_0 = -2$。

请注意，这里 $2$ 并不是一个奇数素数。

本翻译由 AI 自动生成