Counting Unique Islands

You are given T test cases. For each test case, a grid of size N × M consisting of 0's and 1's is provided. A cell with a value of 1 represents land, while 0 represents water.

An island is defined as a group of adjacent land cells (cells with value 1) connected horizontally or vertically. Two cells are part of the same island if there exists a path connecting them via adjacent land cells.

Your task is to determine the number of unique islands in each grid. The solution typically involves using a depth-first search (DFS) or breadth-first search (BFS) approach to traverse the grid and mark visited cells.

Mathematically, if we denote the grid as a matrix \(G\) of size \(N \times M\), then an island is a maximal set \(S = \{(i,j) \mid G_{i,j} = 1\}\) such that for any two cells \((i_1,j_1)\) and \((i_2,j_2)\) in \(S\), there exists a sequence of cells starting from \((i_1,j_1)\) to \((i_2,j_2)\) with consecutive pairs being adjacent (up, down, left, or right).

inputFormat

The input is read from standard input (stdin). The first line contains an integer T (1 ≤ T ≤ 10), the number of test cases. For each test case, the first line contains two integers N and M (1 ≤ N, M ≤ 1000), indicating the number of rows and columns of the grid 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, print a single line on standard output (stdout) containing the number of islands found in the grid.## sample

2
2 2
1 1
1 1
3 3
1 0 1
0 1 0
1 0 1

1
5