Counting Islands in a Grid

Given a grid of dimensions (M \times N) consisting of characters '1' and '0', where '1' represents land and '0' represents water. Two cells are connected if they are adjacent horizontally or vertically. An island is defined as a maximal group of connected lands.

Your task is to determine the number of islands present in the grid.

Mathematically, if we denote the grid as (G), then the number of islands is given by $$\text{Islands} = f(G)$$ where (f) is the function that counts connected components of '1's.

inputFormat

The input begins with an integer (T) on the first line, representing the number of test cases.

For each test case, the first line contains two integers (M) and (N), representing the number of rows and columns, respectively. This is followed by (M) lines, each containing (N) space-separated characters (either '1' or '0').

outputFormat

For every test case, output the number of islands detected in the grid, each on a separate line.## sample

3
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
3 3
1 1 1
0 1 0
1 1 1
3 3
0 0 0
0 0 0
0 0 0

3
1
0