노멀 교수의 구슬 게임

노멀 교수의 아이 셋이 학교에서 계속 말썽을 부려서 교장이 퇴학을 경고했다. 교장을 달래려고 교수는 전교생이 참여하는 게임을 하나 열기로 했다. 게임 이름은 "구슬을 잃지 마라"다.

아이들은 $M$행 $N$열 격자에 한 칸씩 한 명씩 선다. 각 아이는 구슬을 얼마씩 받아서 시작하고, 받는 개수는 아이마다 다를 수 있다.

게임은 턴 단위로 진행된다. 한 턴은 퇴장 단계와 교환 단계로 이루어진다.

퇴장 단계에서는 구슬이 12개보다 적은 아이와 남은 이웃이 하나도 없는 아이가 게임에서 빠진다. 이웃은 앞, 뒤, 왼쪽, 오른쪽 칸에 붙어 서 있고 아직 게임에 남아 있는 아이다. 격자의 가장자리나 모서리에 선 아이는 이웃이 4명보다 적다. 아이가 빠지면 그 자리는 게임이 끝날 때까지 비어 있고, 그 아이는 더 이상 누구의 이웃도 아니다. 그래서 한 번 퇴장시킨 뒤 두 조건 중 하나에 새로 걸리는 아이가 생길 수 있다. 그런 아이가 더 없을 때까지 퇴장을 반복한다. 빠진 아이는 자기 구슬을 가지고 나가고, 그 구슬은 다시 게임에 들어오지 않는다.

퇴장 단계가 끝난 시점에 남은 아이가 없으면 게임이 끝난다. 아이가 남아 있으면 교환 단계로 넘어가서 남은 아이가 모두 동시에 구슬 12개를 자기 이웃에게 똑같이 나눠 준다. 이 시점에 남은 아이의 이웃 수는 1명 이상 4명 이하이므로 12는 항상 정확히 나누어진다. 교환 단계를 한 번 마치면 교환 횟수가 1 늘어나고 다음 턴이 시작된다.

처음 배치와 각 아이의 구슬 개수가 주어질 때 교환이 몇 번 일어나는지 구하라. 게임이 영원히 끝나지 않으면 운동장에 끝까지 남아서 게임을 계속하는 아이가 몇 명인지 구하라.

진행 순서를 정확히 적으면 다음과 같다.

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
}

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어서 테스트 케이스가 $T$개 주어진다. 각 테스트 케이스의 첫 줄에는 $M$이, 둘째 줄에는 $N$이 주어진다. 그다음 $M$개의 줄에는 각각 그 행에 선 아이들의 구슬 개수가 왼쪽부터 차례로 $N$개씩 공백으로 구분되어 주어진다.

제한

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

각 테스트 케이스마다 한 줄에 Case #x: y turns를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 게임이 끝나기 전에 일어나는 교환 횟수다.

게임이 영원히 끝나지 않으면 그 줄에 대신 Case #x: z children will play forever를 출력한다. $z$는 운동장에 영원히 남아 게임을 계속하는 아이 수다.

$y$가 0이거나 1일 때도 turns를 그대로 쓰고, $z$가 1일 때도 children을 그대로 쓴다.