Problem Description

A rabbit has a rectangular grid of $H \times W$ cells. The cell at the $ i $-th row ( $1 \le i \le H$ ) and the $ j $-th column ( $1 \le j \le W$ ) is referred to as cell $ (i,j) $.

The initial state of cell $ (i,j) $ is represented by the character $ S_{i,j} $, where # indicates that the cell is painted black, and . indicates that it is not painted.

The rabbit received a set of stamps as a Christmas present.

This set of stamps contains $ 10^{10} $ types of stamps, and stamp $ k $ ( $1 \le k \le 10^{10}$ ) can paint a set of cells arranged in a horizontal row every $ p_k $ cells at once. Here, $ p_k $ is the $ k $-th smallest odd prime number. That is, by pressing stamp $ k $ once, you can choose integers $ i $ and $ j_0 $, and paint all cells $ (i,j) $ for which there exists an integer $ a $ such that $ j = j_0 + a * p_k $.

The rabbit wants to use this set of stamps to paint all cells black. What is the minimum number of times the stamps need to be pressed?

Input Format

The input is given from the standard input in the following format:

$ 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} $

Output Format

Output the minimum number of times the stamps need to be pressed to paint all cells black.

Sample Input and Output

Sample Input #1

2 15
.#.##.##.#..##.
########.#.####

Sample Output #1

4

Sample Input #2

5 1
.
.
#
.
.

Sample Output #2

4

Sample Input #3

20 19
#.#.##..#.###.#.#.#
.#.###..#.##.##.##.
#.##..#.##..#..#..#
######.######.####.
.#########.####.###
..###.##..#####.##.
#########.#########
.##.##.#####.##.###
##.#####.#####.##.#
.##.#..##.##.###.##
#.##.##.#..##..#.##
#.##.###.##########
#.######..####.####
.##.##.##..#.##.##.
########.##########
##.########.##.#..#
#.##.##.#####.##.##
#############..####
..#.##..##..#..#.#.
.##.#..#####.##.##.

Sample Output #3

37

Notes/Hints

Constraints

• $1 \le H, W$
• $H * W \le 10^5$
• $ S_{i,j} $ is either . or #

Sample Explanation 1

For example, the stamps can be pressed as follows. Note that $ 2 $ is not an odd prime:
- Press stamp $ 1 $ ( $ p_1 = 3 $ ) with $ i = 1, j_0 = 3 $.
- Press stamp $ 2 $ ( $ p_2 = 5 $ ) with $ i = 1, j_0 = 1 $.
- Press stamp $ 4 $ ( $ p_4 = 11 $ ) with $ i = 2, j_0 = 0 $.
- Press stamp $ 4 $ ( $ p_4 = 11 $ ) with $ i = 2, j_0 = -2 $.

见题面 Input 部分

见题面 Output 部分