## NOVICE42 - Problem 2

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 |