#347. 十六宫数独

十六宫数独（Hexadoku）是 数独的 加强版。

给定一个 的方格盘，其中一部分格子已经填好了符号。你需要在剩余的格子中填入符号，使得：

• 每一行中，0 到 9 以及 a 到 f 共 个符号恰好各出现一次；
• 每一列中，这 个符号恰好各出现一次；
• 每个 的粗线宫（共 个）中，这 个符号恰好各出现一次。

现在给出 个未填满的十六宫数独，请你分别把它们补充完整并输出。

数据保证：每个数独都有且只有一个解。

输入第一行一个整数 ，表示数独的个数。

接下来依次给出 个数独。每个数独占 行，每行一个长度为 的字符串，由数字 0-9、小写字母 a-f 以及 x 组成，表示该行的 个格子；其中 x 表示该格待填，其余字符表示已填好的符号。

相邻两个数独之间用一个空行分隔。

按照输入顺序输出 个完整的数独。每个数独占 行，每行 个字符（0-9、a-f）。

相邻两个数独之间用一个空行分隔。

样例输入

2
bfx6xc842xxxxa0x
dxxx1fxxxx5xcxx7
x73x0xxxexxxxxxf
1xcxxx7xf9x03e48
c2xfexx08x47x5xx
x1a94xxxcxxe8b7x
xxxxxx3x6b0x9xxx
x5d328x7xfxxe0c4
24xxdx1978xxx3fx
x9xbf24excx3xxx1
7d6xbxx81x2fxxe9
f3xxcxxxd09x62xx
xcxx30fxxxx2xxxe
xxxx8x9xxex64cxx
a6xx7x2bxxxdf1x0
exfx6xc59xa8x7xx

dxxxxxexb68740cx
67x84xxa0xxedxbx
fbxx60x8dxxx5xx9
xx04d3xxxac1x76x
9x4xbxxxx2x6xxde
xx5dxxxxx0e8xx7x
xex38x2dxxbx6450
86xxxexxxxxxxb92
7dx5x2904bxx1xxf
x4fx76xx5x9c8xax
xx3be8dfxx02x5x7
1x6ea4xxx7fd0cxx
xx70xxxxx54bexxx
4xb62cx9exx3x1x5
xxxx0xxexxxfxaxc
xcxxxb86x9xx2df4

样例输出

bfe69c842371da05
d8401fe3b65ac927
97350da2e48cb61f
1ac25b76f9d03e48
c2bfe9608d47153a
01a945dfc23e8b76
4e78a13c6b059fd2
65d328b7af19e0c4
245ad61978eb03fc
890bf24e5c637da1
7d6cb3081a2f54e9
f31ec75ad094628b
5c9130fd47b2a86e
3b278a910ef64c5d
a6847e2b35cdf190
e0fd64c591a827b3

d321f9e5b68740ca
679841ca0f5ed2b3
fbac6078d3245e19
e504d3b29ac1f768
9047b53cf216a8de
b25d9a6430e8cf71
ae138f2d7cb96450
86cf1e07a4d53b92
7d85c2904b3a16ef
04f2761b5e9c83ad
ca3be8df61029547
196ea45387fd0c2b
2f703da1c54be986
48b62cf9eda37105
51d9074e286fba3c
3cea5b8619702df4

对于全部数据，，每个数独保证有唯一解。

设每个数独中已填好的符号个数为 （满盘共 格）。本题按子任务（subtask）计分：

共 组测试数据（Subtask 5 含 组，其余各 组）。

提示： 的搜索空间远大于 ，请使用回溯搜索并利用行、列、宫剪枝；每次挑选候选符号最少的格子进行填写（MRV 启发式）可以显著减少搜索量。Subtask 5 提示数更少，建议在 MRV 基础上加上约束传播（naked singles：每次填格后若某格只剩一个候选，立即填入并重复直到没有强迫格）或直接采用 Dancing Links / 精确覆盖求解以获得最佳性能。