Professor Normal's Marble Game

Professor Normal's three children keep causing trouble at school, and the principal is threatening to expel them. To appease the principal, the professor agreed to run one game for every student at the school. The game is called Don't Lose Your Marbles.

The children stand in an $M$ by $N$ grid, one child per cell. Each child starts with some number of marbles, and different children may start with different numbers.

The game runs in turns. A turn has a removal phase and an exchange phase.

In the removal phase, every child who has fewer than 12 marbles and every child who has no remaining neighbor leaves the game. A neighbor is a child who stands in the cell immediately in front, behind, to the left, or to the right, and who is still in the game. A child standing on an edge or in a corner of the grid has fewer than 4 neighbors. Once a child leaves, that cell stays empty until the game is over and that child is nobody's neighbor any more, so one round of removals can make another child match one of the two conditions. Repeat the removals until no such child is left. A child who leaves takes their own marbles out of the game, and those marbles never come back.

If no child is left when the removal phase finishes, the game is over. Otherwise the exchange phase runs: every remaining child simultaneously gives away 12 marbles, split equally among their neighbors. At that point each remaining child has 1 to 4 neighbors, so 12 always divides evenly. Each completed exchange phase adds 1 to the number of exchanges, and then the next turn starts.

Given the initial arrangement and the number of marbles each child starts with, determine how many exchanges take place. If the game never ends, determine how many children stay in the courtyard playing forever.

The exact procedure is the following.

number_of_exchanges = 0
repeat forever {
  while (any child has fewer than 12 marbles or has no neighbor) {
    remove all such children from play
  }
  if (there are no children left in play) {
    the game ends
  }
  simultaneously for each child in play {
    the child shares 12 marbles equally among its neighbors
  }
  number_of_exchanges = number_of_exchanges + 1
}

The first line contains the number of test cases, $T$. $T$ test cases follow. The first line of a test case contains $M$ and the second line contains $N$. The next $M$ lines each contain $N$ space separated integers, the number of marbles for each child in that row of the grid, from left to right.

Limits

• $1 \le T \le 100$
• $1 \le M \le 10$
• $1 \le N \le 10$
• Each child starts with 0 to 100 marbles.

For each test case, output one line containing Case #x: y turns, where $x$ is the test case number starting from 1 and $y$ is the number of exchanges that take place before the game is over.

If the game never ends, output Case #x: z children will play forever on that line instead, where $z$ is the number of children who stay in the courtyard playing forever.

Write turns even when $y$ is 0 or 1, and write children even when $z$ is 1.