Number of Islands Problem Statement

You are given a non-empty grid that consists of only 0s and 1s. Your task is to determine the number of islands in this grid.

An island is defined as a group of 1s (representing land) that are connected horizontally, vertically, or diagonally. Assume that the grid is completely surrounded by 0s, which represent water.

Input:

The first line contains an integer 'T' denoting the number of test cases. Then, each test case follows.
The first line of each test case consists of two space-separated integers, 'N' and 'M', indicating the number of rows and columns of the grid respectively.
The subsequent N lines for each test case contain M space-separated integers representing the rows of the grid.

Output:

For each test case, output a single line containing the number of islands on that grid.
Each test case result must be printed on a separate line.
Note: Implementation should focus on calculating the number of islands, as the output printing is already managed.

Example:

Input:

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

Output:

2
1

Constraints:

• 1 <= T <= 10
• 1 <= N <= 100
• 1 <= M <= 100
• 0 <= grid[i][j] <= 1
• Time limit: 1 sec