관개 라인
시간 제한1초메모리 제한256 MB
심은 칸마다 같은 행이나 열의 급수관을 하나 이상 열도록 여는 줄 수를 최소화합니다.
문제
농장은 직사각형 밭 여러 개로 이루어지고, 밭은 다시 정사각형 구역으로 나뉜다. 돌려짓기를 하므로 한 계절에 어떤 구역에는 작물을 심고 어떤 구역은 쉬게 둔다.
밭마다 관개 시설이 하나씩 있다. 주 급수관이 밭 둘레를 돌고, 밸브가 주 급수관과 가로세로 관개 라인을 연결한다. 관개 라인은 밭의 각 행에 하나, 각 열에 하나씩 있으므로 행 열 밭에는 모두 개가 있다. 밸브를 열면 그 라인에 물이 흐르고, 닫으면 흐르지 않는다. 한 구역에 물을 대려면 그 구역이 속한 행 라인과 열 라인 중 하나만 열려 있으면 된다. 열린 라인 위에서도 물이 필요 없는 구역의 배출구는 막아 둔다.
관리 부담을 줄이려면 열어야 하는 라인 수가 최소여야 한다. 밭의 배치를 읽고, 작물을 심은 모든 구역에 물을 대는 데 필요한 관개 라인의 최소 개수를 구하는 프로그램을 작성하시오.
입력
첫 줄에 테스트 케이스의 개수 ()가 주어진다.
각 테스트 케이스의 첫 줄에는 밭의 행 수 과 열 수 ()이 공백으로 구분되어 주어진다. 이어지는 개 줄에는 길이가 인 0과 1로 된 문자열이 주어진다. 1은 작물을 심은 구역, 0은 쉬는 구역을 뜻한다.
출력
각 테스트 케이스마다 "Case #X: Y" 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 는 열어야 하는 관개 라인의 최소 개수다. 콜론 뒤에는 공백을 하나 둔다.