Street light poles

A city has $r$ horizontal streets and $c$ vertical streets. The two directions cross and form an $r \times c$ grid, and every cell of the grid either holds one light pole (1) or is empty (0). One operation places a light pole on an empty cell, or removes the light pole from a cell that has one.

Change the grid so that both of these conditions hold:

1. Every horizontal street has the same number of light poles.
2. Every vertical street has the same number of light poles.

Compute the minimum number of operations needed to reach both conditions.

The first line has the number of test cases $T$. ($1 \le T \le 1000$)

The first line of each test case has the number of horizontal streets $r$ and the number of vertical streets $c$, separated by a space. ($1 \le r, c \le 40$)

The next $r$ lines each hold a string of length $c$ made only of the characters 0 and 1. If the $j$-th character of the $i$-th line is 1, the cell where horizontal street $i$ meets vertical street $j$ has a light pole. If it is 0, that cell is empty.

For each test case, print one line in the format Case i: R. Here $i$ is the test case number starting from 1, and $R$ is the minimum number of operations needed to reach both conditions. If no grid satisfies the conditions, print -1 in place of $R$.