Goldfish and sudoku

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
0.00%(0/0)
Description:

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.


Input:

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'.


Output:

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.


Sample Input:
2
0100
3012
0320
1043
0003
0000
0320
0100
Sample Output:
2134
3412
4321
1243
1243
3412
4321
2134

Submit