The puzzle game Sudoku is a classical game. In the puzzle, the player is given a partially filled grid. The objective of the game is to fill in the grid such that each row, column, and each of the nine subgrids contain all the digits from to .
Jonathan is playing Sudoku! However, his version of Sudoku is slightly different. He is instead given a partially filled grid, and the objective is to fill in the grid such that each row, column, and each of the four subgrids contain all the digits from to .
He is given of these puzzles. However, since he is too lazy to solve them manually, he has asked you to help him solve them with a computer program!
The first line contains the integer , the number of grids that Jonathan needs solved.
Each of the grids will contain lines consisting of characters, for a total of lines. It is guaranteed the grid will only contain the characters
X means that the cell is unfilled, and you must fill it in with the appropriate value.
For each grid, output lines, the filled in grid. The output should therefore consist of a total of lines.
Any valid solution will be accepted. It is guaranteed each grid will have at least one solution.
Note for Sample
The sample does not respect the constraints. Your solution does not need to produce the correct output on the sample to get AC. In particular, the sample has while the actual test data will have .
3 1234 4321 2413 3142 1234 4XX1 2XX3 3142 231X 142X 413X XXXX
1234 4321 2413 3142 1234 4321 2413 3142 2314 1423 4132 3241
Explanation for Sample
The third case in the sample is:
The only possible filled-in grid would be: