Channel

Joe, a former champion coder, has finally bought the farm. No, he is alive and well. He used his programming competition winnings to buy his ancestral farm. He hopes to retire and spend the rest of his days tending cows. For some reason, he now considers himself an expert on cows.

Sadly, his plans will not work out. The farm sits in a cold northern climate, too cold for cows. The land is also dry and poor for growing crops. Joe realizes he must build an irrigation scheme for his field. The scheme diverts part of a river into a long, winding channel through the field. Crops nearest the channel will thrive, so the longer the channel, the better.

The field is a long rectangular strip divided into unit squares. Each square is either dirt, marked '.', or an immovable rock, marked '#'. The channel is one square wide. It enters at the upper left corner and exits at the lower right corner. The channel cannot pass through rocks. The channel must never touch itself, even at a corner, or the water will seep through and take a shortcut. Figure 3 and Figure 4 show examples of the channel touching itself.

Joe's best programming days are long behind him. His straightforward solution is far too slow. Can you help him find the optimal placement of this channel?

The input consists of several test cases, at most 20. Each test case starts with a line containing $r$, the number of rows ($2 \le r \le 20$), and $c$, the number of columns ($2 \le c \le 9$). The next $r$ lines each contain a string of length $c$ describing the field. The last test case is followed by a line containing two zeros.

For each test case, print the case number in the form Case 1:, then print $r$ lines showing the longest possible channel placement. Use 'C' for the channel. There is always a unique solution. Follow the format of the sample output. Print a blank line after the output of each test case.