Alphabet Cake (Large)

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

Each child wants one piece of cake that holds their own initial and no other child's initial. The piece must be a rectangle cut along the grid lines. Assign every blank cell to one child so that this works out. An answer always exists. You do not have to split the cake evenly, and some child may end up with a 1×1 piece. Call it a life lesson about unfairness.

The first line holds the number of test cases $T$. $T$ test cases follow. Each one begins with a line holding two integers $R$ and $C$. Then come $R$ lines of $C$ characters each, describing the cake. Each character is either an uppercase English letter, which means your assistant already wrote that letter on that cell, or ?, which means the cell is blank.

Limits

• $1 \le T \le 100$
• $1 \le R \le 25$
• $1 \le C \le 25$
• Each test case grid holds at least one letter.
• Within one grid, no letter appears on more than one cell.
• At least one answer exists for each test case.

For each test case, print Case #x: on its own line, where $x$ is the test case number starting at 1. Then print $R$ lines of $C$ characters each. The printed grid must keep every letter of the input grid where it was and replace every ? with one uppercase English letter, meaning that cell belongs to the slice of the child with that initial. You may not use a letter that does not appear in the input grid. For each letter, the cells holding that letter must form one rectangle aligned with the grid.

Several grids can satisfy those conditions, so only the grid produced by the following rule counts as correct.

1. In every row that holds at least one letter, fill each blank that lies to the left of the first letter of that row with that first letter, and fill every other blank with the nearest letter to its left in the same row.
2. Every row that holds no letter copies the completed form of the nearest row above it that holds a letter. If no row above it holds a letter, it copies the nearest row below it that holds a letter.