노멀 교수 (Small2)

노멀 교수의 세 아이가 학교에서 계속 말썽을 부려서, 교장이 퇴학시키겠다고 나섰다. 교장을 달래려고 교수는 전교생이 참여하는 놀이를 하나 준비했다.

놀이 이름은 "구슬을 잃지 마라"다. 아이들은 $M$행 $N$열 격자에 한 칸에 한 명씩 선다. 각 아이는 처음에 구슬을 얼마씩 받는다. 받는 개수는 아이마다 다를 수 있다.

놀이는 턴 단위로 진행된다. 한 턴에 각 아이는 구슬 12개를 자기 이웃에게 똑같이 나눠 준다. 이웃은 바로 앞, 뒤, 왼쪽, 오른쪽 칸에 선 아이다. 격자의 가장자리나 모서리에 선 아이는 이웃이 4명보다 적다.

턴이 시작될 때 구슬이 12개 미만인 아이는 구슬을 주고받기 전에 놀이에서 빠진다. 빠진 아이의 자리는 놀이가 끝날 때까지 비어 있고, 그 이웃은 주고받을 상대가 줄어든다. 이웃이 한 명도 없는 아이도 주고받을 상대가 없으므로 함께 빠진다. 이 제거는 더 빠질 아이가 없을 때까지 반복한다.

이 시점에 남은 아이가 없으면 놀이가 끝난다. 남은 아이가 있으면 모두 주고받을 상대가 있으므로 놀이는 계속된다.

아이들의 처음 배치와 각자가 가진 구슬 개수가 주어진다. 구슬을 주고받는 턴이 몇 번 일어나는지 구하라.

놀이는 다음 절차를 정확히 따른다.

number_of_exchanges = 0
repeat forever {
  while (구슬이 12개 미만이거나 이웃이 0명인 아이가 있다) {
    그런 아이를 모두 놀이에서 제외한다
  }
  if (놀이에 남은 아이가 없다) {
    놀이가 끝난다
  }
  simultaneously for each child in play {
    그 아이는 구슬 12개를 이웃에게 똑같이 나눠 준다
  }
  number_of_exchanges 를 1 늘린다
}

어떤 아이의 이웃이 $k$명이면 그 아이는 각 이웃에게 구슬 $12/k$개를 준다. $k$는 1 이상 4 이하이므로 $12/k$는 항상 정수다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 $M$이 적힌 줄과 $N$이 적힌 줄로 시작한다. 이어지는 $M$개의 줄에는 그 행에 선 아이가 가진 구슬 개수가 공백으로 구분되어 $N$개씩 주어진다.

제한

• $1 \le T \le 100$
• $1 \le M \le 40$
• $1 \le N \le 40$
• 각 아이가 처음 가진 구슬은 $0$개 이상 $10^{12}$개 이하이다.

각 테스트 케이스마다 한 줄에 Case #x: y turns를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 놀이가 끝날 때까지 일어난 구슬 교환 횟수다. 놀이가 영원히 끝나지 않으면 대신 Case #x: z children will play forever를 출력한다. $z$는 운동장에 영원히 남아 놀이를 계속하는 아이의 수다. $y$가 1일 때도 turns를 그대로 출력한다.