题目描述
数独是一项非常简单的任务。如图所示,具有9行和9列的方形表被分成9个较小的正方形3x3。在一些单元格中写入从1到9的十进制数字,其他单元格为空。目标是用1到9的十进制数字填充空单元格,每个单元格一个数字,这样在每行,每列和每个标记的3x3子方格中,所有数字从1到9出现。编写程序来解决给定的任务。
输入描述
输入多组数据(最多100组),第一行输入一个整数,表示数据组数。对于每组数据,后面跟着9行,对应于表格的行。在每一行上给出一串9位十进制数字,对应于该行中的单元格。如果单元格为空,则表示为0。
输出描述
对于每个测试用例,你的程序应以与输入数据相同的格式打印解决方案。必须根据规则填充空单元格。如果解决方案不是唯一的,则程序可以打印其中任何一个。
样例输入
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
样例输出
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
提示