가로등 배치

도시에 가로 도로 $r$개와 세로 도로 $c$개가 있다. 두 방향의 도로가 만나 $r \times c$ 격자를 이루고, 격자의 각 칸에는 가로등이 한 개 서 있거나(1) 아무것도 없다(0). 작업 한 번으로 빈 칸에 가로등을 세우거나, 가로등이 있는 칸에서 가로등을 치울 수 있다.

다음 두 조건을 모두 만족하도록 격자를 바꾸려고 한다.

1. 모든 가로 도로의 가로등 개수가 같다.
2. 모든 세로 도로의 가로등 개수가 같다.

두 조건을 만족시키는 데 필요한 작업 횟수의 최솟값을 구하라.

첫째 줄에 테스트 케이스 개수 $T$가 주어진다. ($1 \le T \le 1000$)

각 테스트 케이스의 첫 줄에는 가로 도로 개수 $r$과 세로 도로 개수 $c$가 공백으로 구분되어 주어진다. ($1 \le r, c \le 40$)

이어지는 $r$개의 줄에는 0과 1로만 이루어진 길이 $c$의 문자열이 한 줄씩 주어진다. $i$번째 줄의 $j$번째 문자가 1이면 $i$번 가로 도로와 $j$번 세로 도로가 만나는 칸에 가로등이 있고, 0이면 그 칸은 비어 있다.

각 테스트 케이스마다 한 줄에 Case i: R 형식으로 출력한다. $i$는 1부터 시작하는 테스트 케이스 번호이고, $R$은 두 조건을 만족시키는 데 필요한 작업 횟수의 최솟값이다. 조건을 만족하는 격자를 만들 수 없으면 $R$ 자리에 -1을 출력한다.