Cell Counting

Interview

Time limit3sMemory limit256 MB

Summary

Count the isolated # pixels with no # neighbor in any of the eight directions in each grid.

Level: Easy3 of 10
Topics: Matrix, Implementation
Solved: No attempts yet

Problem

Studying a cancer drug includes counting how many cancer cells are left in a tissue sample once the drug has been applied. The better the drug works, the fewer cells remain. To make that count fast and accurate, you are writing a program that counts the cancer cells in a photograph of the tissue.

The photograph is a two dimensional grid of pixels. An empty pixel is written as . and a pixel that is not empty is written as #. A cancer cell is far smaller than the other organs caught in the same photograph, so it always appears as exactly one # pixel, and two cancer cells never touch. Two or more # pixels touching each other are therefore not a cancer cell but some other organ in the tissue.

Two pixels touch when they are neighbours in one of the eight directions, horizontal, vertical or diagonal. A single # pixel with no # in any of its eight neighbours is one cancer cell. Count the cancer cells in the photograph.

Input

The input holds at most 1,000 test cases.

The first line of each test case has the number of rows $r$ and the number of columns $c$ ( $0 < r, c < 101$ ). The next $r$ lines hold the photograph, one row per line, each a string of length $c$ made only of . and #.

A first line holding two zeros ends the input. That line is not a test case.

Output

For each test case, print the number of cancer cells you counted, one per line.

Examples5

Example 1

Input

5 6
......
....#.
....#.
...#..
#.....
4 3
...
.#.
...
#.#
0 0

Expected output

1
3

Example 2
Input
```
1 1
#
1 1
.
0 0
```
Expected output
```
1
0
```

Example 3

Input

5 5
#####
#####
#####
#####
#####
0 0

Expected output

Example 4

Input

5 5
#.#.#
.#.#.
#.#.#
.#.#.
#.#.#
0 0

Expected output

Example 5
Input
```
1 9
#.#.#.#.#
0 0
```
Expected output
```
5
```