404528: GYM101532 H Corrupted Images

Husam has a lot of free time, so he is using this time in repairing corrupted binary images.

A Binary image can be represented as 2-dimensional array consisting of n rows, each of which is divided into m columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to m from left to right. Each cell is identified by a pair (x, y), which means that the cell is located at row x and column y. The possible values in the binary images are either zero or one.

A binary image is good if all cells in the first row, last row, first column, and last column are ones. Otherwise, the binary image is corrupted. If the binary image is corrupted, Husam will fix it.

Husam wants to fix the image with the minimum number of moves, such that in each move he can swap the values at two different cells.

Can you help Husam by calculating the minimum number of required moves to fix the image?

The first line contains an integer T, where T is the number of test cases.

The first line of each test case contains two integers n and m (3 ≤ n, m ≤ 50), where n is the number of rows in the binary image, and m is the number of columns in each row.

Then n lines follow, each line contains m characters, giving the binary image. All values in the binary image are either zero or one.

For each test case, print a single line containing -1 if Husam cannot fix the binary image. Otherwise, print the minimum number of required moves to fix the image.

3
3 3
111
101
111
4 4
1111
0111
1000
1111
4 5
10101
01010
10101
01010

0
2
-1

In the first test case, the image is good. In the second test case, Husam needs to swap the values of cells (2, 1) and (2, 2), and swap the values of cells (2, 3) and (3, 4), in order to fix the image.