Island Counter

You are given a rectangular grid of size \(n \times m\) where each cell is either water (represented by 0) or land (represented by 1). Your task is to determine the number of islands in the grid. An island is defined as a group of adjacent land cells (i.e. cells with value 1) that are connected horizontally or vertically.

Formally, if we define a cell \( (i,j) \) with \(1\) as land, then two cells \( (i_1, j_1) \) and \( (i_2, j_2) \) belong to the same island if there exists a sequence of cells connecting them such that each consecutive pair is adjacent (up, down, left, or right). In other words, the number of islands is the number of connected components of cells with value \(1\).

inputFormat

The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains two integers (n) and (m) denoting the number of rows and columns respectively. This is followed by (n) lines, each containing (m) space-separated integers (either 0 or 1) representing the grid.

outputFormat

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

1
3 3
1 0 0
0 0 0
0 0 1

2