지뢰 배치

MineLayer는 R행 C열 격자에서 진행하는 MineSweeper와 비슷한 퍼즐 게임이다. 격자의 각 칸에는 지뢰가 하나 있거나 지뢰가 전혀 없다. MineLayer 퍼즐은 숫자로 이루어진 격자로 구성되며, 각 숫자는 인접한 모든 칸과 그 숫자가 있는 칸에 놓인 지뢰의 총개수를 나타낸다. 따라서 숫자의 범위는 영부터 아홉까지이다.

MineLayer의 목표는 주어진 단서와 일치하도록 격자에 지뢰를 배치하는 방법을 알아내는 것이다.

아래는 일반적인 3행 4열 격자이다. 왼쪽에는 원래 배치가 있고 오른쪽에는 퍼즐이 있다.

해가 여러 개일 수 있으므로, 가운데 행에 놓일 수 있는 지뢰의 최대 개수를 출력하는 프로그램을 작성해야 한다. 행의 개수는 항상 홀수이며, 퍼즐에는 항상 적어도 하나의 해가 존재한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ N ≤ 50. 각 퍼즐에는 적어도 하나의 해가 있음이 보장된다.

작은 데이터 세트 (테스트 세트 1 - 공개)

R = 3 또는 R = 5. 3 ≤ C ≤ 5.

큰 데이터 세트 (테스트 세트 2 - 비공개)

R은 3 이상 49 이하인 홀수이다. 3 ≤ C ≤ 49.

입력의 첫 줄에는 테스트 케이스의 개수 N이 주어진다. 이어서 N개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 수가 주어진다. R은 행의 개수이고 C는 열의 개수이다. R은 항상 홀수인 정수이다. 이어지는 R개의 각 줄에는 해당 행의 단서를 나타내는 C개의 수가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 "Case #X: Y"을 포함하는 한 줄을 출력한다. 이때 X는 1부터 시작하는 테스트 케이스 번호이고, Y는 주어진 제약 조건을 만족하는 격자의 가운데 행에 놓일 수 있는 지뢰의 최대 개수이다.