Count the Number of Islands

You are given a grid of size n × m consisting of characters '1' (land) and '0' (water). Your task is to count the number of islands in the grid. An island is defined as a group of adjacent lands connected in all 8 directions (horizontal, vertical, and diagonal). In other words, for a cell at position \((i, j)\), its neighbors are all cells at positions \((i+\delta_i, j+\delta_j)\) where \(\delta_i, \delta_j \in \{-1, 0, 1\}\) and \((\delta_i, \delta_j) \neq (0, 0)\).

The grid is provided as n strings of length m each. Your solution should read input from standard input and output the results to standard output.

inputFormat

The input starts with an integer T (the number of test cases). For each test case, the first line contains two integers n and m separated by a space, representing the number of rows and columns of the grid respectively. This is followed by n lines, each containing a string of length m consisting of characters '0' and '1'.

Example:

2
4 5
11110
11010
11000
00001
3 3
111
010
111

outputFormat

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

Example Output:

2
1

## sample

2
4 5
11110
11010
11000
00001
3 3
111
010
111

2
1

</p>