描述

数独是一项非常简单的任务。如图中所示，一个有 $9$ 行 $9$ 列的正方形桌子被分成 $9$ 个 $3 \times 3$ 的小正方形。在一些单元格中，写入了从 $1$ 到 $9$ 的十进制数字。其他单元格为空。目标是用从 $1$ 到 $9$ 的十进制数字填充空单元格，每个单元格一位数字，这样在每一行、每一列和每个标记的 $3 \times 3$ 子方块中，都会出现从 $1$ 到 $9$ 的所有数字。编写一个程序来解决给定的 Sudoku 任务。

输入

输入数据将以测试用例的数量开始。对于每个测试用例，后面有 $9$ 行，对应于表的行。在每一行上，给出了一个正好 $9$ 个十进制数字的字符串，对应于该行中的单元格。如果单元格为空，则用 $0$ 表示。

输出

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

输入数据 1

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

输出数据 1

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

来源

2005 年东南欧