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 void main(String[] args) throws Exception {
        new Main().run();}

    int q[] = new int[1000000];
    int size =0;
    int rt = 1;

    int pos[];

    void offer(int v){
        q[++size] = v;
        pos[v] = size;
        for(int i=size;i>1;i>>=1){
            if(compare(q[i], q[i>>1]) < 0){

                int t = q[i];q[i] = q[i>>1];q[i>>1] = t;

                pos[q[i]] = i;
                pos[q[i>>1]] = i>>1;

            }else break;
        }
    }

    int poll(){
        int r = q[rt];
        q[rt] = q[size--];
        pos[q[rt]] = rt;
        for(int u=rt,v = rt<<1;v<=size;u = v,v<<=1){
            if(v+1<=size&&compare(q[v+1],q[v]) < 0 ) v++;
            if(compare(q[v], q[u]) < 0 ){
                int t = q[u]; q[u] = q[v]; q[v] = t;
                pos[q[u]] = u;
                pos[q[v]] = v;
            }else break;
        }
        return r;
    }

    int sz(){
        return size;
    }


    public int compare(int x, int y ) {
        int v1 = Math.abs(f[x][1]-f[f[x][3]][1]);
        int v2 = Math.abs(f[y][1]-f[f[y][3]][1]);
        if(v1!=v2){
            return Integer.compare(v1, v2);
        }
        return Integer.compare(f[x][4], f[y][4]);
    }

    public void remove(int idx){
        if(pos[idx]==0) return;

        for(int i=pos[idx];i>1;i>>=1){
            int ci = i>>1;
            int v = q[ci];
            q[i] = v;
            pos[v] = i;
        }
        q[rt] = q[size--];
        pos[q[rt]] = rt;
        for(int u=rt,v = rt<<1;v<=size;u = v,v<<=1){
            if(v+1<=size&&compare(q[v+1],q[v]) < 0 ) v++;
            if(compare(q[v], q[u]) < 0 ){
                int t = q[u]; q[u] = q[v]; q[v] = t;
                pos[q[u]] = u;
                pos[q[v]] = v;
            }else break;
        }

        pos[idx] = 0;
    }


    int f[][];


    int[] get(int i,int j,char x[][]){
        for(int a=0;a<x.length;++a){
            for(int b=0;b<x[0].length;++b){
                if(x[i][j]==x[a][b] && (a!=i||b!=j)){
                    return new int[]{ a, b};
                }
            }
        }
        return new int[]{0,0};
    }

    public int minDistance(String word1, String word2) {
        int l1 = word1.length();
        int l2 = word2.length();
        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        int[][] d = new int[l1+1][l2+1];
        for(int j=1;j<=l2;j++){
            d[0][j] = j;
        }
        for(int i=1;i<=l1;i++){
            d[i][0] = i;
        }

        for(int i=1;i<=l1;i++){
            for(int j=1;j<=l2;j++){
                if(w1[i-1]==w2[j-1]){
                    d[i][j] = d[i-1][j-1];
                }else{
                    d[i][j] = Math.min( 1+ d[i-1][j],Math.min(1+d[i-1][j-1],1+d[i][j-1]));
                }
            }
        }
        return d[l1][l2];
    }

    void solve() {

        int t = ni();

        for(int i=0;i<t;++i){
            char c[][] = nm(9,9);


            for(int j=0;j<3;++j) {
                for (int k = 0; k < 3; ++k) {
                    int x = j + k * 3;
                    int y = j * 3 + k;
                    int num = c[x][y] - '0' + 1;
                    if(num==10){
                        num = 1;
                    }
                    c[x][y] = (char) (num + '0');
                }
            }
            for(int j=0;j<9;++j){
                for(int k=0;k<9;++k){
                    print(c[j][k]);
                }
                println();
            }





        }





    }

    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    int gcd(int a,int b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
        //   is  = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P3119_6.in");
        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) ) { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private void print(Object obj){out.print(obj);}
    private void println(Object obj){out.println(obj);}
    private void println(){out.println();}
}