You are to solve the classic 9x9 sudoku problem.

Input

The first line contains only one number - number of test cases (more than 1 and less then 15). Then the test cases are given. Each of them is given by 81 numbers (from 0 to 9) separated by single white space (new line after each 9th number). Zero means that it is to solve by your program.

Output

In case of there does not exist the solution write "No solution". If there exist 81 number being the solution of sudoku problem, you have to write all those 81 numbers (separated like in input).

Example

Input:
2
0 0 0 0 6 9 8 3 0
9 8 0 0 0 0 0 7 6
6 0 0 0 3 8 0 5 1
2 0 5 0 8 1 0 9 0
0 6 0 0 0 0 0 8 0
0 9 0 3 7 0 6 0 2
3 4 0 8 5 0 0 0 9
7 2 0 0 0 0 0 6 8
0 5 6 9 2 0 0 0 0

0 0 0 0 6 9 8 3 0
9 8 0 0 0 0 0 7 6
6 0 0 0 3 8 0 5 1
2 0 5 4 8 1 0 9 0
0 6 0 0 0 0 0 8 0
0 9 0 3 7 0 6 0 2
3 4 0 8 5 0 0 0 9
7 2 0 0 0 0 0 6 8
0 5 6 9 2 0 0 0 0

Output:
5 1 2 7 6 9 8 3 4
9 8 3 5 1 4 2 7 6
6 7 4 2 3 8 9 5 1
2 3 5 6 8 1 4 9 7
1 6 7 4 9 2 3 8 5
4 9 8 3 7 5 6 1 2
3 4 1 8 5 6 7 2 9
7 2 9 1 4 3 5 6 8
8 5 6 9 2 7 1 4 3
No solution