Joe，一位前冠军程序员，终于买下了农场。不，他活得好好的；他只是用他参加编程竞赛赢得的奖金买下了祖传的农场。他希望退休后余生都能照顾奶牛（不知为何，他现在认为自己是奶牛专家）。

遗憾的是，Joe 简单的田园梦想未能实现。他的农场位于寒冷的北方气候区——这对奶牛来说太冷了！更糟糕的是，这里气候干燥，不适合种植农作物。Joe 现在意识到他必须为他的田地建立一套灌溉系统。该方案涉及将部分河流引入他田地中一条长而蜿蜒的渠道。由于靠近渠道的农作物会长势更好，因此渠道越长越好。

他的田地是一块长方形的土地，被划分为单位正方形。每个正方形要么是泥土，用 ‘.’ 表示，要么是不可移动的岩石，用 ‘#’ 表示。灌溉渠道宽为一个单位，从左上角进入他的土地，并从右下角离开。当然，渠道不能穿过岩石。重要的是，这条渠道绝不能接触到自身，即使是在拐角处也不行（否则水会渗漏并走捷径）。图 3 和图 4 包含了渠道接触到自身的例子。

图 3 和图 4

不幸的是，Joe 最好的编程时光早已过去。他有一个直接的解决方案，但事实证明它太耗时了。你能帮他找出这条渠道的最佳布局吗？

输入包含多个测试用例。每个测试用例以一行开始，包含 $r$（他田地的行数，$2 \le r \le 20$）和 $c$（列数，$2 \le c \le 9$）。接下来的 $r$ 行每行包含一个长度为 $c$ 的字符串，描述他的田地。

最后一个测试用例后跟一行包含两个零。

对于每个测试用例，显示案例编号。在接下来的 $r$ 行中，展示如何在田地中放置最长的渠道，并遵守上述限制。使用字符 ‘C’ 表示渠道。总会有一个唯一的解决方案。按照样例输出的格式进行输出。在每个测试用例的输出后打印一个空行。

样例

输入 1

3 3
.#.
...
.#.
6 7
.......
.......
.......
....#..
.......
.#.....
0 0

输出 1

Case 1:
C#.
CCC
.#C

Case 2:
CCCCCCC
......C
CCCCCCC
C...#..
CCC.CCC
.#CCC.C