지뢰 찾기 마스터

지뢰 찾기는 1980년대에 인기를 끈 컴퓨터 게임이고, 일부 Microsoft Windows 버전에는 지금도 들어 있다. 이 문제는 같은 규칙을 쓰지만, 게임을 해 본 적이 없어도 풀 수 있다.

$R \times C$ 격자에서 게임을 한다. 모든 칸은 처음에 덮여 있다. 서로 다른 $M$개의 칸에 지뢰가 하나씩 숨어 있고, 나머지 칸에는 지뢰가 없다. 원하는 칸을 눌러서 열 수 있다. 지뢰가 있는 칸을 열면 게임이 끝나고 진다. 지뢰가 없는 칸을 열면 그 칸에 0 이상 8 이하의 숫자가 나오고, 이 숫자는 인접한 칸 가운데 지뢰가 있는 칸의 개수다. 두 칸은 변이나 꼭짓점을 공유하면 인접하다. 열린 칸의 숫자가 0이면 인접한 칸이 모두 자동으로 열리고, 새로 열린 칸의 숫자가 또 0이면 같은 일이 반복된다. 지뢰가 없는 칸이 모두 열리면 게임이 끝나고 이긴다.

예를 들어 판이 다음과 같이 놓였다고 하자. '*'는 지뢰, 'c'는 처음 누른 칸이다.

* . . * . . . * * .
. . . . * . . . . .
. . c . . * . . . .
. . . . . . . . * .
. . . . . . . . . .

누른 칸에 인접한 지뢰가 없으므로 그 칸은 0이 되고 인접한 여덟 칸이 함께 열린다. 열림이 계속 번지면 판은 다음과 같이 된다.

* . . * . . . * * .
1 1 1 2 * . . . . .
0 0 0 1 2 * . . . .
0 0 0 0 1 1 1 1 * .
0 0 0 0 0 0 0 1 . .

지뢰가 없으면서 아직 덮여 있는 칸('.')이 남아 있으므로, 게임을 이어 가려면 한 번 더 눌러야 한다.

한 번만 눌러서 이기는 것보다 빠른 승리는 없다. 판의 크기 $R \times C$와 지뢰 개수 $M$이 주어질 때, 누르는 칸을 마음대로 고를 수 있다면 한 번만 눌러서 이길 수 있는 배치가 있는지 판정하고, 있으면 그런 배치를 하나 출력한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 다음 $T$개의 줄에 각각 세 정수 $R$, $C$, $M$이 공백으로 구분되어 주어진다.

제한

• $1 \le T \le 140$
• $1 \le R, C \le 50$
• $0 \le M < R \times C$

각 테스트 케이스마다 먼저 "Case #x:" 형식의 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다.

한 번 눌러서 이길 수 있는 배치가 없으면 다음 줄에 Impossible을 출력한다.

배치가 있으면 $R$개의 줄에 각각 $C$개의 문자를 출력한다. 지뢰가 없는 칸은 '.', 지뢰가 있는 칸은 '*', 처음 누르는 칸은 'c'로 적는다. 이기는 배치가 여러 개일 수 있으므로, 다음 네 조건을 모두 만족하는 배치를 출력한다.

1. 처음 누르는 칸은 첫째 줄 첫째 열의 칸이다.
2. 각 줄에서 지뢰가 없는 칸은 첫째 열부터 빈틈없이 이어진다. 처음 누르는 칸도 지뢰가 없는 칸으로 센다.
3. 지뢰가 없는 칸의 개수는 아래 줄로 갈수록 늘어나지 않는다.
4. 앞의 세 조건을 만족하면서 이기는 배치 가운데, $i$번째 줄의 지뢰 없는 칸 개수를 $a_i$라 할 때 수열 $(a_1, a_2, \dots, a_R)$이 사전순으로 가장 큰 것을 출력한다.

한 번 눌러서 이길 수 있는 배치가 하나라도 있으면, 네 조건을 모두 만족하는 배치도 있다.