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.math.*;


import static java.lang.Math.*;

 public class Solution implements Runnable {
     
    public void solve() throws Exception {
         int t=sc.nextInt();
         while(t-->0)
         {
             
             String arr[]=new String[9];
             for(int i=0;i<9;i++)
             {
            	 arr[i]=sc.nextToken();
             }
             arr[0]=arr[0].replace(arr[0].charAt(0), arr[0].charAt(1));
             arr[1]=arr[1].replace(arr[1].charAt(3), arr[1].charAt(4));
             arr[2]=arr[2].replace(arr[2].charAt(6), arr[2].charAt(7));
             arr[3]=arr[3].replace(arr[3].charAt(1), arr[3].charAt(2));
             arr[4]=arr[4].replace(arr[4].charAt(4), arr[4].charAt(5));
             arr[5]=arr[5].replace(arr[5].charAt(7), arr[5].charAt(8));
             arr[6]=arr[6].replace(arr[6].charAt(2), arr[6].charAt(3));
             arr[7]=arr[7].replace(arr[7].charAt(5), arr[7].charAt(6));
             arr[8]=arr[8].replace(arr[8].charAt(8), arr[8].charAt(7));
            
             for(int i=0;i<9;i++)
             {
            	 
            		 System.out.println(arr[i]);
            	
            	
             }
             
             
                
            
         
            
         }
    }
             
         
        
        
       
        
        
    
    // public boolean binarysearch(int limit )
    
    static Throwable uncaught;

    BufferedReader in;
    FastScanner sc;
    PrintWriter out;

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            sc = new FastScanner(in);
            solve();
        } catch (Throwable uncaught) {
            Solution.uncaught = uncaught;
        } finally {
            out.close();
        }
    }

    public static void main(String[] args) throws Throwable {
        Thread thread = new Thread(null, new Solution(), "", (1 << 26));
        thread.start();
        thread.join();
        if (Solution.uncaught != null) {
            throw Solution.uncaught;
        }
    }

}

class FastScanner {

    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }

    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }

}