Mine Layer (Large)

Mine Layer is a puzzle much like Minesweeper. The board is an $R \times C$ grid, and every square either holds one mine or holds none.

The puzzle is given as a grid of numbers. Each number counts the mines in that square itself together with the squares next to it in all eight directions. Squares outside the board are not counted, so the numbers run from 0 to 9.

The goal is to find a mine layout that matches every given number.

The picture below shows a $3 \times 4$ grid. The original layout is on the left, and the puzzle built from it is on the right.

A puzzle can have several layouts, so print the largest number of mines the middle row can hold. The number of rows $R$ is always odd, so the middle row is row $(R+1)/2$ counted from the top, and at least one layout always matches the numbers.

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

The first line of each test case contains the number of rows $R$ and the number of columns $C$, separated by a space. $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 matching layout.
• $R$ is an odd number between 3 and 49, inclusive.
• $3 \le C \le 49$

For each test case, print one line in the form Case #X: Y, where $X$ is the 1-based test case number and $Y$ is the largest number of mines the middle row can hold in a layout that matches every given number.