AT_xmascon19_h Stamps 3

[problemUrl]: https://atcoder.jp/contests/xmascon19/tasks/xmascon19_h うさぎは $ 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) $ を全て黒く塗ることができる． うさぎはこのスタンプセットを使って全てのマスを黒く塗ろうとしている． 最小で何回スタンプを押せば良いだろうか？

入力は以下の形式で標準入力から与えられる． > $ 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\ \le\ H,W $ - $ H*W\ \le\ 10^5 $ - $ S_{i,j} $ は `.` または `#` ### Sample Explanation 1 例えば以下のように押せばよい． $ 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 $ として押す．