Counting Islands in a Grid

Given a 2D grid where each cell is either land (1) or water (0), determine the number of islands in the grid. An island is defined as a group of horizontally or vertically connected lands. Once a piece of land is visited, it should be marked (or sunk) to avoid counting it again.

You can solve this problem using a Depth-First Search (DFS) approach. For example, consider the following grid:

\( \begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix} \)

This grid contains 2 islands.

inputFormat

The first line of input contains an integer T, 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 integers (either 0 or 1) representing the grid.

outputFormat

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

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

2