配点 : 100 点
除了图章类型和约束之外,图章 1 至 4 具有相同的问题设置。
問題文
兔子是 它有一个矩形网格 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 该值应乘以 1 按下回车后,有整数 i,j_0 时, 满足j = j_0+a*p_k 对于 a 存在的方格 (i,j) 涂成黑色。
兔子想用这个印章套装将所有方格涂黑。 最少需要按多少次印章呢?
制約
- 1 \le H,W
- H*W \le 10^5
- S_{i,j} 是
您也可以写
.或 至少#
入力
输入是按以下格式从标准输入给出的。
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}
出力
打印将所有方块涂成黑色所需的最少印章数量。
入力例 1
2 15 .#.##.##.#..##. ########.#.####
出力例 1
4
例如可以按如下方式按印章。 2 注意不是奇素数的点。
- 作为印章 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
5 1 . . # . .
出力例 2
4
入力例 3
20 19 #.#.##..#.###.#.#.# .#.###..#.##.##.##. #.##..#.##..#..#..# ######.######.####. .#########.####.### ..###.##..#####.##. #########.######### .##.##.#####.##.### ##.#####.#####.##.# .##.#..##.##.###.## #.##.##.#..##..#.## #.##.###.########## #.######..####.#### .##.##.##..#.##.##. ########.########## ##.########.##.#..# #.##.##.#####.##.## #############..#### ..#.##..##..#..#.#. .##.#..#####.##.##.
出力例 3
37