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.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;
 
public class codeforces implements Runnable
{
static class InputReader
{
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
public InputReader(InputStream stream)
{
this.stream = stream;
}
 
public int read()
{
if (numChars==-1)
throw new InputMismatchException();
if (curChar >= numChars)
{
curChar = 0;
try
{
numChars = stream.read(buf);
}
catch (IOException e)
{
throw new InputMismatchException();
}
               
if(numChars <= 0)              
return -1;
}
return buf[curChar++];
}
     
public String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
public int nextInt()
{
int c = read();
           
while(isSpaceChar(c))
c = read();
 
int sgn = 1;
       
if (c == '-')
{
sgn = -1;
c = read();
}
           
int res = 0;
do
{
if(c<'0'||c>'9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
while (!isSpaceChar(c));
       
return res * sgn;
}
       
public long nextLong()
{
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-')
{
sgn = -1;
c = read();
}
long res = 0;
 
do
{
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
while (!isSpaceChar(c));
return res * sgn;
}
 
public double nextDouble()
{
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-')
{
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.')
{
if (c == 'e' || c == 'E')
return res * Math.pow(10, nextInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
}
if (c == '.')
{
c = read();
double m = 1;
while (!isSpaceChar(c))
{
if (c == 'e' || c == 'E')
return res * Math.pow(10, nextInt());
if (c < '0' || c > '9')
throw new InputMismatchException();
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
   
public String readString()
{
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder res = new StringBuilder();
do
{
res.appendCodePoint(c);
c = read();
}
while (!isSpaceChar(c));
           
return res.toString();
}
     
public boolean isSpaceChar(int c)
{
if (filter != null)
return filter.isSpaceChar(c);
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
     
public String next()
{
return readString();
}
       
public interface SpaceCharFilter
{
public boolean isSpaceChar(int ch);
}
}
public static void main(String args[]) throws Exception
{
new Thread(null, new codeforces(),"Main",1<<27).start();
}
 
public static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
 
public static long findGCD(long arr[], int n)
{
long result = arr[0];
for (int i = 1; i < n; i++)
result = gcd(arr[i], result);
return result;
}
 
static void sortbycolomn(long arr[][], int col)
    {
         
        Arrays.sort(arr, new Comparator<long[]>() {
           
          @Override              
           
          public int compare(final long[] entry1,  
                             final long[] entry2) {
 
           
            if (entry1[col] > entry2[col])
                return 1;
            else
                return -1;
          }
        });  
    }
public long no(int i,long sum,int cntr, long arr[],int N)
{
    if(i==N)
    {
        if(sum != 1 && cntr>0)
            return 1;
        else
            return 0;
    }
    long count = 0;
    count += no(i + 1, sum, cntr, arr, N); 
    count += no(i + 1, sum + arr[i],cntr+1,arr,N);
    return count;
}
public void run()
{
InputReader scan = new InputReader(System.in);
PrintWriter write = new PrintWriter(System.out);
int test_case=scan.nextInt();
while(test_case-->0){
  char sudoku[][] = new char[9][9];
  int i,j;
  for(i = 0;i<9;i++)
  {
      String s = scan.next();
      sudoku[i] = s.toCharArray();
  }
  sudoku[0][0] = sudoku[0][0]=='3'?'4':'3'; 
  sudoku[1][3] = sudoku[1][3]=='3'?'4':'3'; 
  sudoku[2][6] = sudoku[2][6]=='3'?'4':'3'; 
  sudoku[3][1] = sudoku[3][1]=='3'?'4':'3'; 
  sudoku[4][4] = sudoku[4][4]=='3'?'4':'3'; 
  sudoku[5][7] = sudoku[5][7]=='3'?'4':'3'; 
  sudoku[6][2] = sudoku[6][2]=='3'?'4':'3'; 
  sudoku[7][5] = sudoku[7][5]=='3'?'4':'3'; 
  sudoku[8][8] = sudoku[8][8]=='3'?'4':'3';
  for(i=0;i<9;i++)
  {
      for(j=0;j<9;j++)
        write.print(sudoku[i][j]);
      write.println();
  }
}
write.flush();
write.close();
}
}