Shortest Bridge

Every story has an Endgame. This is another such story.

Tony Stark and Thanos live in two different islands. Tony wants to reach Thanos's island in minimum time to save the world.

You are given a 2-D binary array of 'N' rows and 'M' columns. If the element of the array is 1 it means it has land in there else if the element is 0 means it has water in there. There are exactly two islands in this array. In one island Tony lives and in another island, Thanos lives. An island is a 4 – directionally connected component of 1’s.

For example

In the above figure, there are two islands coloured in brown and orange respectively.

Tony wants to build a bridge between these two islands. With the help of Friday Tony can build the bridge by changing 1 or more 0’s to 1’s. Size of the bridge is the number of 0’s changed to 1’s. Tony wants to minimize the size of the bridge as it minimizes time to reach Thanos.

For example

Here Bridge is marked in red colour and 1 is the minimum size of bridge possible.

Tony is busy assembling all the avengers, so he called you to solve this problem.

Input Format

The first line of input contains an integer 'T' representing the number of test cases. Then the 'T' test cases are as follows.

The first line of each test case contains two single-spaced integers ‘N’ and ‘M’, representing the number of rows and columns of the 2-D array, respectively.

For the next 'N' lines, each line contains 'M' space-separated integers (0 or 1), where 0 denotes the water and 1 denotes the land.

Output Format:

For each test case, print the length of the shortest bridge which connects the two islands.

The output for each test case is printed in a separate line.

Note:

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

Constraints:

1 <= T <= 5
1 <= N, M <= 100
0 <= ARR[i][j] <= 1

Where ‘ARR[i][j]’ is the value of the elements of the 2-D array.

Time Limit: 1 sec.

Sample Input 1:

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

Sample Output 1:

1 
2

Explanation For Sample Input 1:

Test Case 1: Cells of the bridge are marked using B.  
0 1 0 0
0 B 0 0
0 1 0 0
1 1 1 1

Here the minimum size of the bridge is 1. So, the answer is 1.

Note: Below shown bridge is also a valid bridge but its size is 3 which is not minimum.
0 1 B 0
0 0 B 0
0 1 B 0
1 1 1 1

Test Case 2: Cells of the bridge are marked using B.  
1 1 0
1 0 0
B B 1

Here the minimum size of the bridge is 2. So, the answer is 2.

Sample Input 2:

1
5 5
0 1 1 1 1
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1

Sample Output 2:

2

Explanation For Sample Input 2:

Test Case 1: 
Cells of the bridge are marked using B.

0 1 1 1 1
0 0 B 0 0
0 0 B 0 0
1 1 1 1 1
1 1 1 1 1

Here the minimum size of the bridge is 2. So, the answer is 2.