Mine Layer (Small)

MineLayer is a Minesweeper style puzzle played on an $R$ by $C$ grid. Each square of the grid holds one mine or no mine at all. A MineLayer puzzle is a grid of numbers, and each number is the total number of mines in every square adjacent to that square plus the square itself. A number is therefore between 0 and 9.

The goal is to find a mine layout that matches the given numbers.

Below is a 3 by 4 grid. The original layout is on the left and the puzzle is on the right.

One grid of numbers can match several layouts, so find the largest number of mines the middle row can hold. The number of rows is always odd, so the middle row is row $(R+1)/2$ from the top. Every puzzle has at least one solution.

The first line contains the number of test cases $N$. $N$ test cases follow.

The first line of each test case contains two space separated numbers: $R$, the number of rows, and $C$, the number of columns. $R$ is always odd. Each of the next $R$ lines contains the $C$ numbers of that row, separated by spaces.

Limits

• $1 \le N \le 50$
• Every puzzle has at least one solution.
• $R = 3$ or $R = 5$
• $3 \le C \le 5$

For each test case, print one line containing "Case #X: Y", where $X$ is the 1 based test case number and $Y$ is the largest number of mines the middle row holds among all layouts that satisfy the given numbers.