One day,Xuemei asked Goldfish some simplified Sudoku puzzles,but it's too difficult for Goldfish to solve,so as his friend,you decided to write a program to help him.
The simplified Sudoku puzzles Xuemei asked Goldfish to solve is a simplify edition of traditional Sudoku.A square table with 4 rows and 4 columns is divided to 4 smaller squares 2 x 2 as shown on the Figure.In some of the cells are written decimal digits from 1 to 4.The other cells are empty.The goal is to fill the empty cells with decimal digits from 1 to 4,one digit per cell,in such way that in each row,in each column and in each marked 2 x 2 subsquare,all the digits from 1 to 4 to appear.Write a program to solve a given Sudoku-task to help Goldfish.
The input data will start with the number of the test cases.For each test case,4 lines follow,corresponding to the rows of the table.On each line a string of exactly 4 decimal digits is given,corresponding to the cells in this line.If a cell is empty it is represented by '0'.
For each test case your program should print the solution in the same format as the input data.The empty cells have to be filled according to the rules.If solutions is not unique,you can print any one of them.
2 0100 3012 0320 1043 0003 0000 0320 0100
2134 3412 4321 1243 1243 3412 4321 2134