Minesweeper Master

Minesweeper is played on a grid of $R$ rows and $C$ columns. Every cell starts hidden. $M$ of the cells hold a mine and the other cells hold nothing.

You click one cell to reveal it. If that cell holds a mine, you lose. Otherwise the cell shows a digit from 0 to 8, the number of neighboring cells that hold a mine. Two cells are neighbors when they share an edge or a corner. When a revealed cell shows 0, all of its neighbors are revealed too, and the same rule applies again to every newly revealed cell that shows 0. You win once every cell without a mine is revealed.

Here is a board before the first click. * is a mine and c is the cell you click.

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

No mine touches the clicked cell, so it shows 0, its 8 neighbors are revealed, and the reveal keeps spreading:

* . . * . . . * * .
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 . .

The cells still drawn as . hold no mine and are still hidden, so this click does not win the game.

You want to win with a single click. Given $R$, $C$ and $M$, place the $M$ mines and choose the cell to click so that the first click wins, or report that no such board exists.

The first line has the number of test cases $T$. Each of the next $T$ lines has three integers $R$, $C$ and $M$ separated by spaces.

Limits:

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

For each test case, print a line Case #x:, where x is the test case number starting from 1. On the next $R$ lines print the board, $C$ characters per line, using . for a cell without a mine, * for a mine, and c for the clicked cell.

Many different boards can win with one click, so print exactly the board these rules pick.

• The clicked cell is the cell in row 1, column 1.
• In every row the cells without a mine fill the left end of that row: if row $i$ holds $a_i$ cells without a mine, they are the cells in columns 1 through $a_i$, and $a_1 \ge a_2 \ge \dots \ge a_R$. The clicked cell is a cell without a mine, so $a_1 + a_2 + \dots + a_R = R \times C - M$.
• Among the boards of this shape that win with one click, print the one whose sequence $(a_1, a_2, \dots, a_R)$ is the greatest in lexicographic order. Make $a_1$ as large as possible, then $a_2$, and so on.

If no board of this shape wins with one click, print Impossible on a single line instead of the board.