Problem Description

Rabbit has a rectangular grid of $H \times W$ cells. The cell in the $i$-th row (where $1 \le i \le H$) and the $j$-th column (where $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.

Rabbit received a set of stamps as a Christmas present.

This set of stamps contains two types of stamps, each of which can paint a set of cells black at once, as shown in the figure below:

Namely,

• Pressing the left stamp once allows you to choose integers $i_0, j_0$, and then paint all cells $(i,j)$ black where $i = i_0 + 5a + 2b$ and $j = j_0 - 2a + 5b$ for some integers $a, b$.
• Pressing the right stamp once allows you to choose integers $i_0, j_0$, and then paint all cells $(i,j)$ black where $i = i_0 + 2a + 5b$ and $j = j_0 - 5a + 2b$ for some integers $a, b$.

Rabbit wants to use these 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

8 8
.####.##
########
.####.##
########
########
##.####.
########
##.####.

Sample Output #1

3

Sample Input #2

50 50
######################.#.##.######################
##############.########################.###..#####
####.###############..############################
###################.###########.####.#############
########.#.#####################.##########..#####
###.###.#####.######.######.##############.###.##.
.########.###.###############..#######.###.####.#.
.#.###############.######.#####.###############..#
####.########################.###.##.#############
################.#####.#.#########.#.#############
..#########.############.#########.#####.######.##
######.###############.#####.###########..########
###.##########.#.##########..################.####
################.###########################.##.##
#####.############.....#####.####..###############
#.#####################.####.#.######..##########.
#########.#.########.#.###.############.##.#######
########.####.####################.#######.#..####
##.#####.####.################.#######.#######.###
..#######.#.#################.###.##############..
#.######.####.#####.#.####.#####.##.#####..#######
################.#######..#####.##################
########.###..#########..###.########.###.######.#
#############################.######.###########.#
##..#############.#############..#########.####.##
############.###########.###.##############..#####
.#####..###############.#########.#.#########.####
#.########.############.#########.############.###
###.#.####################..###########.#..#######
#####.###.##############.##.##########.#####.#####
#######.##.#####.##########.###############.######
.#########.################.#####.#########.######
##.############.###..###########.###.#.##.######.#
##############..#######.#############.######.#####
###.################.###..######.##..#########.###
#.##################.########.########..##########
.#.#########.#####################################
#######.###########.#########.#####.############..
#.####################.##..###.###.###############
###########.############.####..###################
.###########.#########.#################.#########
##############.#..##############..#########.######
###..##.##########################.###########.###
#########.##########.#.#####.####.################
#.######.##.################.#.######.#.#####.####
#########.######.###.#.###.######.###.#.#####.####
###############.##################.#######.#..####
#.######.#######..#############..#########.##.####
#########.###########.####.###########.#########.#
######.#.###########.#####.###.##.#######..######.

Sample Output #2

15

Sample Input #3

1 1
#

Sample Output #3

0

Notes/Hints

Constraints

• $1 \le H, W \le 300$
• $ S_{i,j} $ is either . or #

见题面 Input 部分

见题面 Output 部分