NOVICE42 - Problem 2

no tags 

 

This contest is based on brute force, and where better to apply this technique than in a day to day newspaper game. Hemanshu Bansal has a knack for solving puzzles and he claims that he is very fast always saying that he can solve the problem even before I can start to code. Help me beat him once in for all in this famous game of Sudoku.
The objective of Su Doku puzzles is to replace the blanks in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9.
You will be given a Sudoku puzzle and your program has to print its solution.

This contest is based on brute force, and where better to apply this technique than in a day to day newspaper game. Hemanshu Bansal has a knack for solving puzzles and he claims that he is very fast always saying that he can solve the problem even before I can start to code. Help me beat him once in for all in this famous game of Sudoku. The objective of Su Doku puzzles is to replace the blanks in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9.

You will be given a Sudoku puzzle and your program has to print its solution.

 

 

Input

 

line 1:T(no. of test cases)

line 2: Grid 01

line 3-11: grid of 9x9

line 12: Grid 02

line 13-21: grid of 9x9

....

....

so on.

 

Output

 

line 1: Grid 01(should be same as input)

line 2-10: grid of 9x9(the solution)

line 11: <blank line>

line 12: Grid 02

.......

so on.

In case of multiple solutions print lexicographically minimum solution. Refer to wikipedia for the definition of lexicographical order.

 

Example

Input:
2
Grid 01
003020600
900305001
001806400
008102900
700000008
006708200
002609500
800203009
005010300
Grid 02
200080300
060070084
030500209
000105408
000000000
402706000
301007040
720040060
004010003
Output:
Grid 01
483921657
967345821
251876493
548132976
729564138
136798245
372689514
814253769
695417382

Grid 02
245981376
169273584
837564219
976125438
513498627
482736951
391657842
728349165
654812793


Added by:Mahesh Chandra Sharma
Date:2011-03-01
Time limit:2.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64