11520 - Fill the Square

本題需要你用大寫字母來畫一個正方形。

說的更清楚一點，給定一個正方形方格裡面有許多空白區塊以及已填入字母的區塊，你必須把所有空白區塊用字母填滿，且滿足下列條件：

1. 相鄰的兩個域塊字母不會相同，共用一個邊稱為相鄰。
2. 有許多填入字母的方式，所以必須請你以字典順序最小的方式填入，以"列順序"(row major order)的方式由上而下、由左而右來定先後次序。
   

Input

第一列有一個整數表示測試資料的組數，每組資料一開始會有一個整數 n (n <= 10)，表示正方形的大小，接下來的 n 列，每列會有 n 個字元，字元包含所有大寫字母[A, Z]，及用來表示空白的 “.” 。

Output

請以Case #:(#表示測試資料編號)格式輸出編號，再以矩陣的方式印出所有字母。
 

Sample Input                      Output for Sample Input  

2 3 ... ... ... 3 ... A.. ...

Case 1: ABA BAB ABA Case 2: BAB ABA BAB

---

原文出處