Alphabet Cake (Small)

You are catering a children's party with a cake shaped like a grid of $R$ rows and $C$ columns. Your assistant has written the initial of one child in icing on one cell of the cake, for each child. A cell holds at most one initial, and no two children share an initial, so no letter appears twice.

Each child wants a single rectangular piece that contains their own initial and no other child's initial. The sides of a piece follow the grid lines. Assign every blank cell to one child so that this works out, leaving no cell unassigned. Only inputs that admit such an assignment are given. The cake does not have to be split evenly, and a child may end up with a $1 \times 1$ piece.

The first line contains the number of test cases $T$. $T$ test cases follow. The first line of each test case contains two integers $R$ and $C$ separated by a space. Then $R$ lines of $C$ characters each describe the cake. Each character is either an uppercase English letter or ?. An uppercase letter is an initial already written on that cell, and ? is a blank cell.

Limits:

• $1 \le T \le 100$
• $1 \le R \le 12$
• $1 \le C \le 12$
• $R \times C \le 12$
• The input grid contains at least one letter.
• No letter appears in more than one cell.
• Every test case admits at least one valid assignment.

For each test case, first output one line containing Case #x: and nothing else, where $x$ is the test case number starting from 1. Then output $R$ more lines of $C$ characters each. The output grid must be the input grid with every ? replaced by an uppercase letter that names the child whose piece contains that cell. You may not write a letter that does not appear in the input. For each letter, the cells holding that letter must form one rectangle whose sides follow the grid lines.

Several grids can satisfy those rules, and only one of them is accepted. Read each row left to right and concatenate the rows from top to bottom into a string of length $R \times C$. Output the grid whose string is the lexicographically smallest.