National Treasures

The great hall of the national museum has been robbed several times recently, and everyone is now worried about the security of the treasures on display. To keep the hall safe, the museum hires additional guards to stand inside it and watch over the ancient artifacts. The museum wants to hire the minimum number of additional guards so that the whole hall is secured.

The great hall is a grid of $R \times C$ cells. Some cells are already occupied by the museum's own guards. Every other cell holds an artifact of some type (a statue, a sculpture, and so on). An artifact may be replaced by a newly hired guard, but a guard may never stand on a cell that still holds an artifact, and an artifact may never simply be taken away to leave its cell empty — for each artifact cell you either keep the artifact or swap it for a hired guard.

Each artifact has a set of critical points: cells that must have a guard standing on them if that artifact is to remain in the hall. One guard standing on a cell that is a critical point of several artifacts watches over all of them at once. The critical points of any artifact are always a subset of the 12 cells around it, numbered 1 through 12 as shown below (X marks the artifact itself, and each number marks the critical point with that number):

 .  2  .  3  .
 1  .  9  .  4
 . 12  X 10  .
 8  . 11  .  5
 .  7  .  6  .

The type of an artifact is a non-negative integer whose $i$-th bit — counting from the least significant bit as bit $1$ — is $1$ exactly when critical point number $i$ is a critical point of that artifact. For example, an artifact of type $595$ (binary $1001010011$) has the critical points ${1, 2, 5, 7, 10}$. If a critical point of an artifact lies outside the grid, it is automatically considered secure.

Given the layout of the great hall, find the minimum number of additional guards to hire so that every remaining artifact is secured.

The input contains one or more test cases. Each test case begins with a line holding two integers $R$ and $C$ ($1 \le R, C \le 50$), the dimensions of the hall. Each of the next $R$ lines contains $C$ integers separated by one or more spaces. The $j$-th integer of the $i$-th line is $-1$ if cell $(i, j)$ already holds one of the museum's guards; otherwise it is an integer $T$ ($0 \le T < 2^{12}$) giving the type of the artifact in that cell.

The input ends with a line containing two zeros; this terminating line is not a test case.

For each test case, print one line of the form:

k. G

where $k$ is the test case number (starting from $1$) and $G$ is the minimum number of additional guards that must be hired so that every remaining artifact is secured.