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.util.*;
import java.io.*;
import java.util.stream.*;

public class Problem {
	private static BufferedReader in;
	private static BufferedWriter out;

	public static void main(String[] args) throws IOException {
		open();

		StringTokenizer st;
		StringBuilder ans;

		int t = readInt();
		int i;
		while (t-- > 0) {
			String line;
			ans=new StringBuilder();
			for(i=0;i<9;i++) {
				line=readString();
				line=line.replace('2', '1');
				ans.append(line+"\n");
			}
			out.write(ans+"\n");
		}
		close();
	}

	private static int[] readInts() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	}

	private static int readInt() throws IOException {
		return Integer.parseInt(in.readLine());
	}

	private static long[] readLongs() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
	}

	private static long readLong() throws IOException {
		return Long.parseLong(in.readLine());
	}

	private static double[] readDoubles() throws IOException {
		return Stream.of(in.readLine().split(" ")).mapToDouble(Double::parseDouble).toArray();
	}

	private static double readDouble() throws IOException {
		return Double.parseDouble(in.readLine());
	}

	private static String readString() throws IOException {
		return in.readLine();
	}

	private static int setBit(int S, int j) {
		return S | (1 << j);
	}

	private static int isOn(int S, int j) {
		return S & (1 << j);
	}

	private static int clearBit(int S, int j) {
		return S & ~(1 << j);
	}

	private static int toggleBit(int S, int j) {
		return S ^ (1 << j);
	}

	private static int lowBit(int S) {
		return S & (-S);
	}

	private static int setAll(int n) {
		return (1 << n) - 1;
	}

	private static int modulo(int S, int N) {
		return ((S) & (N - 1));
	} // returns S % N, where N is a power of 2

	private static boolean isPowerOfTwo(int S) {
		return (S & (S - 1)) == 0 ? true : false;
	}

	private static int nearestPowerOfTwo(int S) {
		return ((int) Math.pow(2.0, (int) ((Math.log((double) S) / Math.log(2.0)) + 0.5)));
	}

	private static int turnOffLastBit(int S) {
		return ((S) & (S - 1));
	}

	private static int turnOnLastZero(int S) {
		return ((S) | (S + 1));
	}

	private static int turnOffLastConsecutiveBits(int S) {
		return ((S) & (S + 1));
	}

	private static int turnOnLastConsecutiveZeroes(int S) {
		return ((S) | (S - 1));
	}

	private static void open() {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new BufferedWriter(new OutputStreamWriter((System.out)));
	}

	private static void close() throws IOException {
		out.flush();
		out.close();
		in.close();
	}
}