지뢰 배치 (라지)

지뢰 배치는 지뢰 찾기와 비슷한 퍼즐이다. 판은 $R \times C$ 격자이고, 각 칸에는 지뢰가 한 개 있거나 아예 없다.

퍼즐은 숫자로 채워진 격자로 주어진다. 각 숫자는 그 칸 자신과 그 칸에 여덟 방향으로 이웃한 칸에 놓인 지뢰를 모두 센 값이다. 판 밖은 세지 않으므로 숫자는 0부터 9까지다.

목표는 주어진 숫자와 하나도 어긋나지 않는 지뢰 배치를 찾는 것이다.

아래 그림은 $3 \times 4$ 격자의 예다. 왼쪽이 원래 지뢰 배치이고, 오른쪽이 그 배치에서 만들어진 퍼즐이다.

배치가 여러 가지일 수 있으므로, 가운데 줄에 놓일 수 있는 지뢰 개수의 최댓값을 출력한다. 행의 개수 $R$는 항상 홀수여서 가운데 줄은 위에서 $(R+1)/2$번째 줄이고, 숫자에 맞는 배치는 항상 하나 이상 있다.

첫째 줄에 테스트 케이스의 개수 $N$이 주어진다. 이어서 $N$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에 행의 개수 $R$와 열의 개수 $C$가 공백으로 구분되어 주어진다. $R$는 항상 홀수다. 다음 $R$개의 줄에는 각 행의 숫자가 $C$개씩 공백으로 구분되어 주어진다.

제한

• $1 \le N \le 50$
• 모든 퍼즐에는 숫자에 맞는 배치가 적어도 하나 있다.
• $R$는 3 이상 49 이하의 홀수다.
• $3 \le C \le 49$

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 주어진 숫자에 모두 맞는 배치에서 가운데 줄에 놓일 수 있는 지뢰 개수의 최댓값이다.