Counting Fish Schools

In this problem, you are given a grid of characters representing water cells and fish cells. A cell with a '1' represents part of a fish school, while a cell with a '0' represents water. Two cells are part of the same school if they are horizontally or vertically adjacent (diagonal connections are not considered). Your task is to count the number of distinct fish schools in the grid.

More formally, consider the grid as a matrix ( G ) of size ( M \times N ). Two cells ( G[i][j] ) and ( G[k][l] ) belong to the same school if there exists a sequence of cells ( (i_0, j_0), (i_1, j_1), \ldots, (i_r, j_r) ) such that ( (i_0, j_0) = (i, j) ), ( (i_r, j_r) = (k, l) ), and for each ( t ), the cells ( (i_t, j_t) ) and ( (i_{t+1}, j_{t+1}) ) are adjacent horizontally or vertically.

inputFormat

Input is read from standard input (stdin). The first line contains an integer ( T ), the number of test cases. Each test case starts with a line containing two integers ( M ) and ( N ): the number of rows and columns of the grid. The following ( M ) lines each contain a string of length ( N ) consisting of characters '0' or '1' representing the grid.

outputFormat

For each test case, output a single integer on a new line indicating the number of fish schools found in the grid. The output is written to standard output (stdout).## sample

2
3 3
110
010
001
4 5
11000
11000
00100
00011

2
3