Number of Islands Problem Statement

Given a non-empty grid of 0s and 1s, determine the number of distinct islands. An island is a collection of '1's (land) connected horizontally, vertically, or diagonally. It is assumed that all grid edges are surrounded by water ('0').

Input:

The first line contains an integer ‘T’ denoting the number of test cases. Each test case includes: The first line contains two integers, ‘N’ and ‘M’, representing the grid dimensions. The next N lines contain M integers each, representing the grid rows.

Output:

For each test case, output the total number of islands present in the grid. Each result should be on a new line.

Example:

Input:

2
4 5
1 1 0 0 0
0 1 0 0 1
1 0 0 1 1
0 0 0 0 0
2 2
1 0
0 1

Output:

3
2

Constraints:

• 1 <= T <= 50
• 1 <= N <= 100
• 1 <= M <= 100
• 0 <= grid[i][j] <= 1

Note: You do not need to print the output, simply implement the function as required.