Professor Normal (Small2)

Professor Normal's three children keep causing trouble at school, and the principal is threatening to expel them. To calm the principal down, the professor organized a game for every student in the school.

The game is called "Don't Lose Your Marbles". The children stand on an $M$ by $N$ grid, one child per cell. Each child starts with some number of marbles, and different children may start with different amounts.

The game proceeds in turns. On each turn, every child gives out 12 marbles, shared equally among that child's neighbours. The neighbours of a child are the children standing immediately in front, behind, to the left and to the right. A child standing on an edge or in a corner of the grid has fewer than 4 neighbours.

Any child who has fewer than 12 marbles at the start of a turn is removed from the game before the exchange takes place. The removed child's cell stays empty until the game ends, so the neighbours have fewer children to exchange with. A child with no neighbours is also removed, because there is nobody to exchange with. This removal repeats until no child has to be removed.

If no child is left at that point, the game ends. Otherwise every remaining child has somebody to exchange with, and the game continues.

Given the initial arrangement and the number of marbles each child starts with, count how many marble exchanges take place.

The game follows this procedure exactly.

number_of_exchanges = 0
repeat forever {
  while (any child has < 12 marbles or 0 neighbours) {
    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 neighbours
  }
  increment number_of_exchanges by 1
}

If a child has $k$ neighbours, that child gives $12/k$ marbles to each of them. $k$ is between 1 and 4, so $12/k$ is always an integer.

The first line contains the number of test cases $T$. $T$ test cases follow. Each one starts with a line containing $M$ and then a line containing $N$. The next $M$ lines each contain $N$ space separated integers, the number of marbles held by each child in that row of the grid.

Limits

• $1 \le T \le 100$
• $1 \le M \le 40$
• $1 \le N \le 40$
• Each child starts with at least $0$ and at most $10^{12}$ marbles.

For each test case, print one line containing Case #x: y turns, where $x$ is the test case number starting from 1 and $y$ is the number of marble exchanges that take place before the game is over. If the game never ends, print Case #x: z children will play forever instead, where $z$ is the number of children who stay in the courtyard forever. Print turns unchanged even when $y$ is 1.