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 (number 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:

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