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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;

public class d {
    static BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
       String[] s1=s();
       int t=i(s1[0]);
      StringBuilder sb=new StringBuilder();
       while(t-->0){
          char[] [] a=new char[9][9];
          for(int i=0;i<9;i++){
              a[i]=s()[0].toCharArray();
          }
          a[0][0]=a[0][1];
          a[3][1]=a[3][2];
          a[6][2]=a[6][3];

           a[1][3]=a[1][4];
           a[4][4]=a[4][5];
           a[7][5]=a[7][6];

           a[2][6]=a[2][7];
           a[5][7]=a[5][8];
           a[8][8]=a[8][7];


     StringBuilder sb1=new StringBuilder();
          for(int i=0;i<9;i++){
              for(int j=0;j<9;j++){
                  sb1.append(a[i][j]);
              }sb1.append("\n");
          }sb.append(sb1);
       }
        System.out.println(sb.toString());
    }static long val=0;
    static long dfs(ArrayList<Integer>[] adj,int[] vis,int first,int second,int i,StringBuilder sb,long[][] colors,long x){
        vis[i]=1;int color=0;
       // System.out.println(i);
        if(adj[i].size()==3) return -1;
        if(first+second==1){
            val+=colors[2][i-1];color=2;vis[i]=color+1;

        }else if(first+second==2){
            val+=colors[1][i-1];color=1;vis[i]=color+1;

        }else
        { val+=colors[0][i-1];sb.append(1+" ");color=0;vis[i]=color+1;}
        //System.out.println(color+" "+i);
        for(Integer J:adj[i]){
            if(vis[J]==0){
                dfs(adj,vis,second,color,J,sb,colors,val);
            }
        }return 0;
    }
    static String[] s() throws IOException {
        return s.readLine().trim().split("\\s+");
    }
    static int i(String ss) {
        return Integer.parseInt(ss);
    }
    static long l(String ss) {
        return Long.parseLong(ss);
    }
    static int MAXN;
    static int[] spf;
    static void sieve() {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)
            spf[i] = i;
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;
        for (int i=3; i*i<MAXN; i++)
        {
            if (spf[i] == i)
            {
                for (int j=i*i; j<MAXN; j+=i)

                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }
    static long powerwithmod(long  x, long y, long p) {
        long  res = 1;
        x = x % p;
        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }static long[] fac ;
    static void calculatefac(long mod){
        fac[0]=1;
        for (int i = 1 ;i <= MAXN; i++)
            fac[i] = fac[i-1] * i % mod;
    }
    static long nCrModPFermat(int n, int r, long mod) {
        if (r == 0)
            return 1;
        fac[0] = 1;
        return (fac[n]*
                modInverse(fac[r], mod)
                % mod * modInverse(fac[n-r], mod)
                % mod) % mod;
    }static long modInverse(long a, long m)
    {
        return (powerwithmod(a, m - 2, m));
    }





}

class Student12 {
    int  l;long r;int ind;
    public Student12(int l, long r,int ind) {
        this.l = l;this.ind=ind;
        this.r = r;
    }

    public String toString()
    {
        return this.l+" ";
    }
}
class Sortbyroll12 implements Comparator<Student12> {

    public int compare(Student12 a, Student12 b){
        if(a.l<=b.l) return -1;
     /*   else if(a.r==b.r){
            if(a.r==b.r){
                return 0;
            }
            if(a.r<b.r) return -1;
            return 1;}*/
        return 1;  }
}