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 自动生成**