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:
"""
    Author : thekushalghosh
    Team   : CodeDiggers
    
    I prefer Python language over the C++ language :p :D
    
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,io,os
start_time = time.time()
 
################# ---- USER DEFINED INPUT FUNCTIONS ---- #################
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(s[:len(s)])
def invr():
    return(map(int,input().split()))
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
 
def qw(n):
    n = n + 1
    if n == 10:
        n = 8
    return(str(n))
def solve():
    a = []
    for i in range(9):
        s = insr()
        a.append(list(s))
    a[0][0] = qw(int(a[0][0]))
    a[1][3] = qw(int(a[1][3]))
    a[2][6] = qw(int(a[2][6]))
    a[3][1] = qw(int(a[3][1]))
    a[4][4] = qw(int(a[4][4]))
    a[5][7] = qw(int(a[5][7]))
    a[6][2] = qw(int(a[6][2]))
    a[7][5] = qw(int(a[7][5]))
    a[8][8] = qw(int(a[8][8]))
    for i in range(9):
        print(*a[i],sep = "")
    print()
    
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
def main():
    ONLINE_JUDGE = __debug__
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    t = inp()
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
    sys.stdout.close()
############## ---- USER DEFINED PROGRAMMING FUNCTIONS ---- ##############
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
ONLINE_JUDGE = not __debug__
if ONLINE_JUDGE:
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    out = __pypy__.builders.StringBuilder()
    if sys.version_info[0] < 3:
        os.write(1,out.build())
    else:
        os.write(1,out.build().encode())
main()