One sheep... two sheep...

Interview

Time limit1sMemory limit256 MB

Summary

Count the groups of # cells connected up, down, left, or right in each test grid.

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

Problem

A while ago I could not sleep. I would lie awake staring at the ceiling until morning. One day I told my friend Gwangmin about it, and he said, "Just count sheep!"

I thought that was useless advice. But the next time I lay down and tried to fall asleep, I caught myself counting sheep anyway. Then it occurred to me that I could turn this into a program, so I got out of bed and sat down at the computer.

A sheep is written as # and grass is written as .. A meadow full of grazing sheep then becomes a grid. If two sheep cells touch each other up, down, left, or right, they belong to the same flock. Two cells that touch only at a corner belong to different flocks. One connected blob of # cells is one flock, and a single # with no sheep next to it still counts as a flock of its own.

By the time the grid was drawn I was getting sleepy, but I had to know how many flocks were on it. Given the grid, count the flocks.

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains the grid height $H$ and the grid width $W$ , separated by a space. The next $H$ lines each contain one string of length $W$ . Every character is either # for a sheep or . for grass.

$0 < T \le 100$
$0 < H \le 100$
$0 < W \le 100$

Output

For each test case, print the number of sheep flocks in the grid on its own line, in the order the test cases are given.

Examples5

Example 1

Input

2
4 4
#.#.
.#.#
#.##
.#.#
3 5
###.#
..#..
#.###

Expected output

6
3

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

Example 3

Input

4
1 10
#.#.#.#.#.
1 10
##########
10 1
#
.
#
#
.
#
.
.
#
#
10 1
.
.
.
.
.
.
.
.
.
.

Expected output

Example 4
Input
```
1
5 5
#....
.#...
..#..
...#.
....#
```
Expected output
```
5
```

Example 5

Input

1
15 15
###############
..............#
###############
###############
###############
#..............
###############
###############
###############
..............#
###############
###############
###############
#..............
###############

Expected output