Counting Islands

You are given a grid that represents a map with obstacles and empty cells. Obstacles are denoted by # and empty cells by .. An island is defined as a maximal group of adjacent empty cells, where adjacency is considered only in the four cardinal directions (up, down, left, right). Your task is to calculate the number of islands in the grid for each test case.

You can solve this problem using graph traversal algorithms such as Depth-First Search (DFS) or Breadth-First Search (BFS). Note that cells are connected only if they share a side.

In mathematical terms, if we denote the grid as a matrix \(G\) of size \(n \times m\), then an island is a maximal set \(S\) of indices such that for every \((i, j) \in S\), \(G[i,j] = '.'\) and for any two indices in \(S\) there is a sequence connecting them using steps in \(\{(0,1), (0,-1), (1,0), (-1,0)\}\).

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(t\) (\(1 \le t \le 100\)), the number of test cases. For each test case, the first line contains two integers \(n\) and \(m\) (\(1 \le n, m \le 1000\)), representing the number of rows and columns of the grid respectively. This is followed by \(n\) lines, each containing a string of length \(m\) comprised of the characters # and ..

outputFormat

For each test case, output a single integer on a new line representing the number of islands (groups of connected empty cells) in the corresponding grid. The output should be written to standard output (stdout).

## sample

3
5 5
..##.
#..#.
#..#.
.##..
#####
4 4
####
#..#
#..#
####
1 1
#

3
1
0

</p>