Fill the Square

**题目描述** 在一个$n*n$的网格中填了一些大写字母，你的任务是把剩下的格子中也填满大写字母，使得任意两个相邻的格子(即有公共边的格子)中的字母不同。如果有多种填法，则要求按照从上到下，从左到右的顺序把所以格子连接起来得到的字符串的字典序应该尽量小。 **输入格式** 输入的第一行为测试数据的组数$T$.每组数据的第一行为$n(1<=10)$,即网格的行数和列数；以下$n$行每行$n$个字符，表示整个网格。为了清楚起见，本题用小数点表示没有填字母的格子。 **输出格式** 对于每组数据，输出填满字母后的网格 感谢@洛谷万岁 提供的翻译

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2515 [PDF](https://uva.onlinejudge.org/external/115/p11520.pdf) 



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

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