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 PYTHON3):

Solution:
import sys
import math
#input=sys.stdin.readline
# mod inverse ref:geeks for geeks
#link:https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
mod=998244353
def power(x, y, p) : 
    res = 1     # Initialize result 
  
    # Update x if it is more 
    # than or equal to p 
    x = x % p  
      
    if (x == 0) : 
        return 0
  
    while (y > 0) : 
          
        # If y is odd, multiply 
        # x with result 
        if ((y & 1) == 1) : 
            res = (res * x) % p 
  
        # y must be even now 
        y = y >> 1      # y = y/2 
        x = (x * x) % p 
          
    return res 
def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
    return x         
t=int(input())
for _ in range(t):
    #n=int(input())
    #n,a,b=map(int,input().split())
    #a=list(map(int,input().split()))
    d={}
    for i in range(9):
        d[i]=[]
        s=''
        s=input()
        #print(s)
        for j in range(9):
            d[i].append(s[j])
    d[1][1]=d[1][0]
    d[2][5]=d[1][3]
    d[0][6]=d[0][5]
    d[4][2]=d[4][0]
    d[5][4]=d[3][5]
    d[3][8]=d[5][7]
    d[7][0]=d[7][1]
    d[8][3]=d[6][5]
    d[6][7]=d[6][6]
    for i in range(9):
        for j in range(9):
            print(d[i][j],end="")
        print()