Counting Islands

You are given multiple test cases. For each test case, you are provided with a grid representing a map. The grid consists of characters '1' (land) and '0' (water). An island is formed by a group of adjacent lands connected horizontally or vertically.

The input begins with an integer T, the number of test cases. For each test case, the first line contains two integers n and m which denote the number of rows and columns of the grid. This is followed by n lines, each containing a string of length m representing the grid.

Your task is to determine the number of islands in each grid and output the result on a new line for each test case.

The problem can also be expressed mathematically as follows:

Given a grid \(G\) where \(G[i][j]\) \(\in \{0,1\}\), find the number of connected components (islands) in \(G\) where the connectivity relation is defined as:

\[ (i_1, j_1) \sim (i_2, j_2) \quad \text{if} \quad |i_1-i_2|+|j_1-j_2| = 1 \]

inputFormat

The first line contains an integer T, the number of test cases.

For each test case:

• The first line contains two integers n and m, representing the number of rows and columns.
• The next n lines each contain a string of length m consisting of '0' and '1' characters that represent water and land respectively.

outputFormat

For each test case, output a single integer on a new line representing the number of islands in the grid.

## sample

1
5 5
11000
11000
00000
00011
00011

2

</p>