Sudoku (As Good As Lee Hsien Loong)

Prime Minister of Singapore, Lee Hsien Loong (李顯龍), can write a program to solve the Sudoku, and as CS majors in this top university, let's do it!

Lee's code consists of 200+ lines; no worries - our sample code for this particular Sudoku problem consists of only 63 (yes, only 26 minus 1) lines. Try it and prove that you're as good as Lee Hsien Loong!

(source: http://digital.asiaone.com/sites/default/files/original\_images/May2015/20150506\_pmleecoding\_fb\_zb.jpg)

Solve the Sudoku! See input/output below.

Input

The first line contains an integer, N (1 ≤ N ≤ 10), which indicates the number of test cases (i.e., Sudoku puzzles) in the following. Each test case contains 9 lines, and each line contains 9 numbers. Each number ranges from 0 to 9, and 0's represent empty boxes - boxes to be filled/solved.

Output

For each Sudoku puzzle, print one valid completed grid, preserving every given digit and using digits 1 through 9 exactly once in every row, column and 3-by-3 box. Print nine rows of nine space-separated digits. If no solution exists, print NO.

The archived sample includes a puzzle with multiple valid completions. Any valid completion is accepted; it need not match the sample grid exactly.

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

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