지뢰 배치 (작은 입력)

MineLayer는 $R \times C$ 격자에서 하는 지뢰 찾기 계열 퍼즐이다. 격자의 각 칸에는 지뢰가 하나 있거나 아예 없다. MineLayer 퍼즐은 숫자로 채워진 격자로 주어지고, 각 숫자는 그 칸에 인접한 모든 칸과 그 칸 자신에 놓인 지뢰의 총 개수를 뜻한다. 따라서 숫자는 0 이상 9 이하다.

퍼즐의 목표는 주어진 숫자와 맞아떨어지는 지뢰 배치를 찾는 것이다.

아래는 3행 4열 격자의 예다. 왼쪽이 원래 지뢰 배치이고, 오른쪽이 퍼즐로 주어지는 숫자 격자다.

숫자 격자 하나에 맞는 배치가 여러 개일 수 있으므로, 가운데 행에 놓일 수 있는 지뢰의 최대 개수를 구한다. 행의 개수는 항상 홀수이므로 가운데 행은 위에서 $(R+1)/2$번째 행이다. 모든 퍼즐에는 해가 적어도 하나 있다.

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

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

제한

• $1 \le N \le 50$
• 모든 퍼즐에는 해가 적어도 하나 있다.
• $R = 3$ 또는 $R = 5$
• $3 \le C \le 5$

각 테스트 케이스마다 한 줄에 "Case #X: Y"를 출력한다. $X$는 1부터 시작하는 테스트 케이스 번호이고, $Y$는 주어진 숫자 격자를 만족하는 배치 가운데 가운데 행의 지뢰 개수가 가장 많은 경우의 그 개수다.