Find the perimeter

You are given a map of an island. Your task is to find the perimeter of the island. The map is represented by a binary grid where ‘0’ represents water, and ‘1’ represents the land.

Note:

There is only one island and water surrounding it. There are no lakes, i.e., all the water is connected. Each edge of the land is 1 unit.

For example:

You are given map = [[0, 0, 0, 0, 0],
                     [0, 0, 1, 0, 0],
                     [0, 1, 1, 1, 0],
                     [0, 0, 1, 0, 0]]

You are given the map as:

Here, it can be clearly seen the perimeter of the island is 12. Hence the answer is 12.

Input Format:

The first line of input contains a single integer ‘T’, representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of rows and columns in the given map.

The following ‘N’ lines of each test case contain ‘M’ space-separated integers representing each row of the map.

Output Format:

For each test case print a single integer value representing the perimeter of the given island in the map.

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

Constraints:

1 <= T <= 10
1 <= N, M <= 10^3
map[i][j] == 1 or 0

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Sample Input 1:

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