在 $n$ 行 $m$ 列的矩形棋盘（传统上为 $8 \times 8$）上的骑士巡游（knight's tour）是指用整数 $1$ 到 $n \times m$ 对棋盘上的方格进行标记，使得标签 $n+1$ 位于标签 $n$ 的骑士移动步长处。也就是说，水平移动 $2$ 格且垂直移动 $1$ 格，或者水平移动 $1$ 格且垂直移动 $2$ 格。下图展示了一个 $8 \times 8$ 的骑士巡游。

如果骑士巡游（在方形棋盘上）每一行和每一列的数值之和都相等（对于 $8 \times 8$ 的情况，该和为 $260$），则称其为（半）幻方骑士巡游。对于本题，你将获得一系列已移除许多标签的半幻方 $8 \times 8$ 骑士巡游（见下图）。请编写一个程序来填补缺失的标签，使该骑士巡游成为半幻方。

输入格式

输入的第一行包含一个十进制整数 $P$ ($1 \le P \le 10000$)，表示后续的数据集数量。每个数据集应被独立处理。

每个数据集包含多行输入。第一行包含数据集编号 $K$。接下来的 $8$ 行，每行包含 $8$ 个以空格分隔的整数，给出了对应行的标签。如果标签值为 $-1$，则表示该标签已被移除，你的程序需要找到填入该位置的正确数值。

输出格式

对于每个数据集，输出 $9$ 行。第一行输出数据集编号 $K$。接下来的 $8$ 行应包含 $8$ 个以空格分隔的整数，填补移除的值，以给出一个完整的半幻方骑士巡游，且该巡游必须包含输入中给出的正数标签。可能存在多个正确答案。如果你的结果是一个半幻方骑士巡游，且输入中的正数标签在你的答案中位于相同位置，则你的结果将被评为正确。

样例

输入 1

1
1
1 48 -1 -1 33 -1 63 18
30 51 -1 3 -1 -1 -1 -1
-1 -1 -1 -1 15 -1 -1 -1
-1 -1 -1 45 -1 -1 36 -1
-1 -1 25 -1 9 -1 21 60
-1 -1 -1 -1 24 57 12 -1
-1 6 -1 -1 39 -1 -1 -1
54 -1 42 -1 -1 -1 -1 -1

输出 1

1
1 48 31 50 33 16 63 18 
30 51 46 3 62 19 14 35 
47 2 49 32 15 34 17 64 
52 29 4 45 20 61 36 13 
5 44 25 56 9 40 21 60 
28 53 8 41 24 57 12 37 
43 6 55 26 39 10 59 22 
54 27 42 7 58 23 38 11

说明

你的输出不必像上述样例输出那样对齐。只需确保每个数据集的 $8$ 行输出中，每行数值之间至少有一个空格，且不超过两个空格即可。