Problem Description

The rabbit has a rectangular grid of $H \times W$ cells. The cell in 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) $.

Initially, some of the cells are painted black. The information about cell $ (i,j) $ is represented by the character $ S_{i,j} $, where # means it is painted black, and . means it is not painted.

The rabbit received a stamp as a Christmas present.

Pressing this stamp once can paint all the cells in the set shown in the figure below black. To be more detailed, it is an infinitely connected straight line of a $19 \times 31$ pattern enclosed by a red frame. However, the stamp can only be pressed by translating it in $ 1 $ cell units, and it cannot be rotated, flipped, or pressed with a $ 0.5 $ cell offset.

The rabbit wants to use this stamp to paint all the unpainted cells black. What is the minimum number of times the stamp needs 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 stamp needs to be pressed to paint all the cells black.

Sample Input and Output

Sample Input #1

19 31
..#############################
#...###########################
###..##########################
####...########################
######...######################
########..#####################
#########...###################
###########...#################
#############..################
##############...##############
################..#############
#################...###########
###################...#########
#####################..########
######################...######
########################...####
##########################..###
###########################...#
#############################..

Sample Output #1

1

Sample Input #2

5 5
###.#
##..#
##.##
#..##
#.###

Sample Output #2

4

Sample Input #3

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

Sample Output #3

13

Notes/Hints

Constraints

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

见题面 Input 部分

见题面 Output 部分