지뢰 찾기 마스터

지뢰 찾기는 $R$행 $C$열 격자에서 하는 게임이다. 처음에는 모든 칸이 덮여 있고, 그중 $M$개 칸에 지뢰가 있다. 나머지 칸에는 지뢰가 없다.

칸 하나를 클릭하면 그 칸이 열린다. 지뢰가 있는 칸을 클릭하면 진다. 지뢰가 없는 칸을 클릭하면 그 칸에 이웃한 칸 가운데 지뢰가 있는 칸의 수가 0부터 8까지의 숫자로 나타난다. 두 칸이 변이나 꼭짓점을 맞대고 있으면 이웃이다. 열린 칸의 숫자가 0이면 이웃한 칸이 모두 함께 열리고, 새로 열린 칸의 숫자가 0이면 같은 규칙이 다시 적용된다. 지뢰가 없는 칸이 모두 열리면 이긴다.

다음은 첫 클릭 직전의 판이다. *는 지뢰, c는 클릭할 칸이다.

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

클릭한 칸에 이웃한 지뢰가 없으므로 숫자 0이 나타나고, 이웃한 8칸이 열리며 열림이 계속 번진다.

* . . * . . . * * .
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$, $C$, $M$이 주어지면 지뢰 $M$개를 놓고 클릭할 칸을 정해서 첫 클릭에 이기는 판을 만들거나, 그런 판이 없음을 알린다.

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

제한:

• $1 \le T \le 230$
• $1 \le R, C \le 10$
• $0 \le M < R \times C$

각 테스트 케이스마다 Case #x: 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 그다음 $R$개 줄에 판을 한 줄에 $C$글자씩 출력한다. 지뢰가 없는 칸은 ., 지뢰가 있는 칸은 *, 클릭할 칸은 c로 나타낸다.

한 번의 클릭으로 이기는 판은 여러 가지이므로, 다음 규칙이 정하는 판을 그대로 출력한다.

• 클릭할 칸은 1행 1열 칸이다.
• 각 행에서 지뢰가 없는 칸은 그 행의 왼쪽 끝부터 이어진다. $i$행에 지뢰가 없는 칸이 $a_i$개라면 그 칸은 1열부터 $a_i$열까지이고, $a_1 \ge a_2 \ge \dots \ge a_R$이다. 클릭할 칸도 지뢰가 없는 칸이므로 $a_1 + a_2 + \dots + a_R = R \times C - M$이다.
• 이 모양의 판 가운데 한 번의 클릭으로 이기는 것이 여럿이면, 수열 $(a_1, a_2, \dots, a_R)$이 사전순으로 가장 큰 판을 출력한다. $a_1$을 최대로 하고, 그다음 $a_2$를 최대로 하는 식이다.

이 모양의 판 가운데 한 번의 클릭으로 이기는 것이 없으면, 판 대신 Impossible을 한 줄에 출력한다.