说明

这是一道Special Judge题，Sepcial Judge Module By stong9070

题目描述

数独是一项非常简单的任务。如下图所示，一张9行9列的表被分成9个3×3的小方格。在一些单元格中写上十进制数字1～9，其他单元格为空。目标是用1～9的数字填充空单元格，每个单元格一个数字，这样在每行、每列和每个被标记为3×3的子正方形内，所有1～9的数字都会出现。编写一个程序来解决给定的数独任务。

输入格式

输入数据将从测试用例的数量开始。对于每个测试用例，后面都跟9行，对应表的行。在每一行上都给出9个十进制数字，对应这一行中的单元格。如果单元格为空，则用0表示。

输出格式

对于每个测试用例，程序都应该以与输入数据相同的格式打印解决方案。空单元格必须按照规则填充。如果解决方案不是唯一的，那么程序可以打印其中任何一个。

样例

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

来源

POJ2676