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.lang.reflect.Array;
import java.util.*;
import java.lang.*;
import java.io.*;

public class ct1 {
    static class Activity {
        int sTime = -1, eTime = -1;
        char doer = 'N';
    }

    static class Moment {
        int c, j;

        Moment(int c, int j) {
            this.c = c;
            this.j = j;
        }
    }

    static class Sorter implements Comparator<Integer> {

        @Override
        public int compare(Integer a, Integer b) {
            if (a == b)
                return 0;
            int x = a, y = b;
            int counta = 0, countb = 0;
            int firsta = 0, firstb = 0;
            while (x != 0 || y != 0) {
                if (y != 0) {
                    firstb = y % 10;
                    y /= 10;
                    countb++;
                }
                if (x != 0) {
                    firsta = x % 10;
                    x /= 10;
                    counta++;
                }
            }
            if (firsta > firstb)
                return -1;
            else if (firstb > firsta)
                return 1;
            else {
                if (counta > countb)
                    return 1;
                else if (counta < countb)
                    return -1;
                else {
                    if (a > b)
                        return -1;
                    else
                        return 1;
                }
            }
        }

    }


    public static String largestNumber(final List<Integer> A) {
        Collections.sort(A, new Sorter());
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < A.size(); i++) {
            res.append(A.get(i));
        }
        return res + "";
    }

    public static void main(String[] args) {
        Scanner inp = new Scanner(System.in);
        int n = inp.nextInt();
        while(n-->0){
            StringBuilder[] a = new StringBuilder[9];
            for(int i=0; i<9; i++){
                a[i] = new StringBuilder();
                a[i].append(inp.next());
            }
            res(a);
            for(int i=0; i<9; i++){
                System.out.println(a[i]);
            }
        }
    }

    static void res(StringBuilder[] a){
        increment(a, 0, 0);
        increment(a, 1, 3);
        increment(a, 2, 6);
        increment(a, 3, 1);
        increment(a, 4, 4);
        increment(a, 5, 7);
        increment(a, 6, 2);
        increment(a, 7, 5);
        increment(a, 8, 8);

    }

    static void increment(StringBuilder[] a, int i, int j){
        int x = Integer.parseInt(a[i].charAt(j)+"");
        if(x<9)
            a[i].setCharAt(j, (char)(x+1+48));
        else
            a[i].setCharAt(j, (char)(49));
    }
}