Count Islands

Given a 2D grid of characters where each cell is either '1' (land) or '0' (water), your task is to count the number of islands. An island is a group of adjacent lands connected horizontally or vertically. Diagonal connections do not count.

This problem can be solved using the Depth-First Search (DFS) algorithm. For each cell that contains a '1', perform a DFS to mark all connected land cells as visited (by setting them to '0') and increment the island count.

Formally, if we denote the grid as \(G\) with dimensions \(m \times n\), an island is defined as a maximal set of indices \(\{(i,j)\}\) such that for any two indices \((i_1,j_1)\) and \((i_2,j_2)\) in the set, there exists a path of adjacent indices in the set connecting them. Here, two indices \((i,j)\) and \((i',j')\) are considered adjacent if and only if \(|i-i'| + |j-j'| = 1\>.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case starts with two integers \(M\) and \(N\), where \(M\) is the number of rows and \(N\) is the number of columns in the grid. This is followed by \(M\) lines, each containing a string of length \(N\) consisting of the characters '0' and '1'.

outputFormat

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

## sample

2
4 5
11110
11010
11000
00000
4 5
11000
11000
00100
00011

1
3

</p>