Description

You have a photo of a sea area with $N \times N$ pixels. . means ocean, and # means land, as shown below:

.......
.##....
.##....
....##.
..####.
...###.
.......

A piece of land connected in the four directions (up, down, left, right) forms an island. For example, the picture above has $2$ islands.

Because global warming causes sea levels to rise, scientists predict that within the next few decades, the edge of each island, within a range of one pixel, will be submerged by seawater. Specifically, if a land pixel is adjacent to the ocean (among its four neighboring pixels in up, down, left, right, there is ocean), then it will be submerged.

For example, the sea area above will become the following in the future:

.......
.......
.......
.......
....#..
.......
.......

Please compute: according to the scientists' prediction, how many islands in the photo will be completely submerged.

Input Format

The first line contains an integer $N$. $(1 \le N \le 1000)$.

The following $N$ lines with $N$ characters per line represent a photo of the sea area.

The photo guarantees that the pixels in row $1$, column $1$, row $N$, and column $N$ are all ocean.

Output Format

Output one integer representing the answer.

7 
.......
.##....
.##....
....##.
..####.
...###.
.......  

1

Hint

Time limit: 1 second, 256M. Lanqiao Cup, 9th Provincial Contest, 2018.

Translated by ChatGPT 5