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:
t= int(input())

while(t):
    
    row1=input()
    row2=input()
    row3=input()
    row4=input()
    row5=input()
    row6=input()
    row7=input()
    row8=input()
    row9=input()


    val = int(row1[0])
    if val==9:
        val=1
    else:
        val+=1
    
    row1 = str(val) + row1[1:]

    val = int(row2[4])
    if val==9:
        val=1
    else:
        val+=1
    
    row2 = row2[:4] + str(val) + row2[5:]

    val = int(row3[8])
    if val==9:
        val=1
    else:
        val+=1
    
    row3 = row3[:8]+str(val) + row3[9:]

    val = int(row4[1])
    if val==9:
        val=1
    else:
        val+=1
    
    row4 = row4[:1]+str(val) + row4[2:]

    val = int(row5[5])
    if val==9:
        val=1
    else:
        val+=1
    
    row5 = row5[:5] + str(val) + row5[6:]

    val = int(row6[6])
    if val==9:
        val=1
    else:
        val+=1
    
    row6 = row6[:6] + str(val) + row6[7:]

    val = int(row7[2])
    if val==9:
        val=1
    else:
        val+=1
    
    row7 = row7[:2] + str(val) + row7[3:]

    val = int(row8[3])
    if val==9:
        val=1
    else:
        val+=1
    
    row8 = row8[:3] + str(val) + row8[4:]

    val = int(row9[7])
    if val==9:
        val=1
    else:
        val+=1
    
    row9 = row9[:7] + str(val) + row9[8:]

    print(row1)
    print(row2)
    print(row3)
    print(row4)
    print(row5)
    print(row6)
    print(row7)
    print(row8)
    print(row9)

    t -=1