You have been given a non-empty grid consisting of only 0s and 1s. You have to find the number of islands in the given grid.

An island is a group of 1s (representing land) connected horizontally, vertically or diagonally. You can assume that all four edges of the grid are surrounded by 0s (representing water).

Input Format:

The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first input line of each test case contains two single space-integers ‘N’ and ‘M’ representing the number of rows and columns of the grid, respectively.

From the second line of each test case, the next N lines represent the rows of the grid. Every row contains M single space-separated integers.

Output Format:

For each test case, the only line of output will print the number of islands in the grid.

Print the output of each test case in a separate line.

Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

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

Time limit: 1 sec