Minesweeper Master

Minesweeper is a computer game that became popular in the 1980s, and some versions of Microsoft Windows still include it. This problem uses the same rules, but you can solve it without ever having played the game.

You play on an $R \times C$ grid. Every cell is hidden at the start. One mine is hidden in each of $M$ different cells, and no other cell holds a mine. You may click any cell to reveal it. If the revealed cell holds a mine, the game ends and you lose. Otherwise the revealed cell shows a digit between 0 and 8, the number of neighboring cells that hold a mine. Two cells are neighbors when they share an edge or a corner. If a revealed cell shows 0, all of its neighbors are revealed automatically, and the same happens again for every newly revealed cell that shows 0. When every cell without a mine has been revealed, the game ends and you win.

For example, suppose the board starts like this, where '*' is a mine and 'c' is the clicked cell.

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

The clicked cell has no neighboring mine, so it shows 0 and its eight neighbors are revealed with it. The reveal keeps spreading, and the board becomes this.

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

Cells that hold no mine are still hidden (the '.' characters), so you have to click again to continue the game.

Nothing is quicker than winning in one click. Given the board size $R \times C$ and the number of mines $M$, and given that you choose which cell to click, decide whether some arrangement lets you win in one click, and print one such arrangement when it exists.

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

Limits

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

For each test case, first print a line of the form "Case #x:", where $x$ is the test case number starting from 1.

If no arrangement wins in one click, print Impossible on the next line.

Otherwise print $R$ lines of $C$ characters each. Write '.' for a cell without a mine, '*' for a cell with a mine, and 'c' for the clicked cell. Several arrangements can win in one click, so print the one that meets all four conditions below.

1. The clicked cell is the cell in the first row and the first column.
2. In every row the cells without a mine run from the first column with no gap. The clicked cell counts as a cell without a mine.
3. The number of cells without a mine never grows as you move down the rows.
4. Among the arrangements that win in one click and meet the first three conditions, print the one whose sequence $(a_1, a_2, \dots, a_R)$ is largest in lexicographic order, where $a_i$ is the number of cells without a mine in row $i$.

Whenever some arrangement wins in one click, an arrangement meeting all four conditions also exists.