SUDOGOB - Sudoku goblin

no tags 

A sudoku goblin has read your book with sudoku problems. He has erased or added some numbers from settings. Your task is to write a program that can detect modified settings.

For every sudoku setting you have to count number of possible solutions and in the case that it is equal to 1 print

the unique solution.

Input

There is a number T of the test cases on the first line followed by T sudoku tables separated by one empty line. One sudoku table consists of 9 lines of 9 numbers 0-9 separated by one space. Zero in the table marks the empty field.

Output

For every test case, one line with number of possible solutions optionally followed by solved sudoku in the same format as on the input.

Example

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

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

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

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

hide comments
David: 2020-03-30 18:04:40

Can't quite find solution!

Last edit: 2021-04-20 17:52:30
[Rampage] Blue.Mary: 2017-09-04 03:26:44

The number of possible solutions is relatively "small" in all test cases.


Added by:dRak
Date:2013-03-04
Time limit:1s-10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 BF WHITESPACE