Problem: You are given a correct solution of the sudoku puzzle. If you don't know what is the sudoku, you can read about it [here](http://tiny.cc/636xmz).

The picture showing the correct sudoku solution:

<image>

Blocks are bordered with bold black color.

Your task is to change at most 9 elements of this field (i.e. choose some 1 ≤ i, j ≤ 9 and change the number at the position (i, j) to any other number in range [1; 9]) to make it anti-sudoku. The anti-sudoku is the 9 × 9 field, in which:

  * Any number in this field is in range [1; 9]; 
  * each row contains at least two equal elements; 
  * each column contains at least two equal elements; 
  * each 3 × 3 block (you can read what is the block in the link above) contains at least two equal elements. 



It is guaranteed that the answer exists.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case consists of 9 lines, each line consists of 9 characters from 1 to 9 without any whitespaces — the correct solution of the sudoku puzzle.

Output

For each test case, print the answer — the initial field with at most 9 changed elements so that the obtained field is anti-sudoku. If there are several solutions, you can print any. It is guaranteed that the answer exists.

Example

Input


1
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563


Output


154873396
336592714
729645835
863725145
979314628
412958357
631457992
998236471
247789563

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;  
public class main {	
	public static long solve(int n)
	{
		long f=1;
		long l=100000;
		while(f<l)
		{
			long m=(f+l)/2;
			/*System.out.println(f+ " " +l);
			System.out.println(m);
			System.out.println((m*(m+1)/2));*/
			if((long)(m*(m+1)/2)>=n)
			{
				l=m;
			}
			else
			{
				f=m+1;
			}
		}
		return f;
	}
	public static void main(String[] args) throws NumberFormatException, IOException
	{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw= new PrintWriter(System.out);
		int t = Integer.parseInt(br.readLine());
		ArrayList<Pair> arr = new ArrayList<main.Pair>();
		arr.add(new Pair(0, 0));
		arr.add(new Pair(1, 3));
		arr.add(new Pair(2, 6));
		arr.add(new Pair(3, 1));
		arr.add(new Pair(4, 4));
		arr.add(new Pair(5, 7));
		arr.add(new Pair(6, 2));
		arr.add(new Pair(7, 5));
		arr.add(new Pair(8, 8));
		for (int i = 0; i < t; i++) {
			char[][] grid = new char[9][9];
			for (int j = 0; j < grid.length; j++) {
				String s = br.readLine();
				for (int k = 0; k < grid.length; k++) {
					grid[j][k]=s.charAt(k);
				}
			}
			for (int j = 0; j < arr.size(); j++) {
				if(arr.get(j).y==8)grid[arr.get(j).x][arr.get(j).y]=grid[arr.get(j).x-1][arr.get(j).y];
				else grid[arr.get(j).x][arr.get(j).y]=grid[arr.get(j).x][arr.get(j).y+1];
			}
			for (int j = 0; j < grid.length; j++) {
				for (int k = 0; k < grid.length; k++) {
					pw.print(grid[j][k]);
				}
				pw.println();
			}
		}
		pw.close();
	}
	static class Pair
	{
		int x; int y;
		public Pair(int x, int y){
			this.x=x;this.y=y;;
		}
	}
}