The puzzle game Sudoku is a classical game. In the puzzle, the player is given a partially filled ~9 \times 9~ grid. The objective of the game is to fill in the grid such that each row, column, and each of the nine ~3 \times 3~ subgrids contain all the digits from ~1~ to ~9~.

An example of a solved ~9\times 9~ Sudoku grid.

Jonathan is playing Sudoku! However, his version of Sudoku is slightly different. He is instead given a partially filled ~4 \times 4~ grid, and the objective is to fill in the grid such that each row, column, and each of the four ~2 \times 2~ subgrids contain all the digits from ~1~ to ~4~.

He is given ~Q~ 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!

Input Specification

The first line contains the integer ~Q~ ~(1 \le Q \le 5 \times 10^5)~, the number of grids that Jonathan needs solved.

Each of the ~Q~ grids will contain ~4~ lines consisting of ~4~ characters, for a total of ~4Q~ lines. It is guaranteed the grid will only contain the characters 1, 2, 3, 4, and X. X means that the cell is unfilled, and you must fill it in with the appropriate value.

Output Specification

For each grid, output ~4~ lines, the filled in grid. The output should therefore consist of a total of ~4Q~ lines.

Any valid solution will be accepted. It is guaranteed each grid will have at least one solution.

Subtasks

Let ~C~ be the number of Xs.

Subtask 1 [15%]

~0 \le C \le 3~

Subtask 2 [30%]

~4 \le C \le 7~

Subtask 3 [40%]

~8 \le C \le 11~

Subtask 4 [15%]

~12 \le C \le 16~

Sample Input

3
1234
4321
2413
3142
1234
4XX1
2XX3
3142
231X
142X
413X
XXXX

Sample Output

1234
4321
2413
3142
1234
4321
2413
3142
2314
1423
4132
3241

Explanation for Sample

Note that passing the sample is not required to pass some of the subtasks.

The third case in the sample is:

The only possible filled-in grid would be:

Notes

Please note that the input for this problem is extremely large. Because of this, it is recommended to read and use the IO tips.

In particular:

Python users

• Please use PyPy instead of CPython, as there is more than a 6x speed increase.
• Append the following line to the top of your code for faster IO (more than a 4x speed increase):
  • import sys; input = sys.stdin.readline
  • For more details, check out the tips page.

Java users

• Please use java.io.BufferedReader instead of java.util.Scanner.
  • For more details, check out the tips page.

C/C++ users

• Please use scanf or untie the cin stream.
  • For more details, check out the tips page.
• For a 2x speed increase, you should use getchar() to read in the grids instead of scanf or cin.