Counting Islands

You are given a 2D grid composed of '1's (land) and '0's (water). An island is defined as a group of adjacent lands connected horizontally or vertically. Your task is to count the number of islands in the grid.

More formally, given a grid of dimensions \(m \times n\), an island is a maximal set of cells such that each cell is a '1' and any two cells in the island are connected by a path consisting of adjacent (up, down, left, right) '1's.

The input will consist of multiple test cases. For each test case, the first line contains two integers \(m\) and \(n\). The next \(m\) lines each contain \(n\) integers (either 0 or 1) separated by spaces. For each test case, print the number of islands on a new line.

The DFS (depth-first search) algorithm can be used to traverse and mark visited cells.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• For each test case:
• The first line contains two integers \(m\) and \(n\) indicating the dimensions of the grid.
• The next \(m\) lines each contain \(n\) space-separated integers (each either 0 or 1) representing the grid.

It is guaranteed that all numbers are separated by single spaces.

outputFormat

For each test case, output a single line containing one integer: the number of islands found in the grid.

## sample

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

2
2

</p>