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:
#!/usr/bin/env python3
import sys

# test with
# printf "1\n154873296\n386592714\n729641835\n863725149\n975314628\n412968357\n631457982\n598236471\n247189563\n" | ./anti-sudoku.py 
# printf "2\n192476358\n867539421\n345821976\n759368214\n416792835\n238145769\n921683547\n673954182\n584217693\n476358192\n539421867\n821976345\n368214759\n792835416\n145769238\n683547921\n954182673\n217693584\n" | ./anti-sudoku.py
#Function to print the grid
def printGrid():
    global grid
    for row in grid:
        for char in row:
            sys.stdout.write(str(char))
        sys.stdout.write('\n')

# #Function to check if a digit can be placed in the given block
# def possible(row,col,digit):
#     global grid
#     #for i in range(0,9):
#     #    if grid[row][i] == digit:
#     #       return False
#     if digit not in grid[row]:
#         return False
#     # for i in range(0,9):
#     #     if grid[i][col] == digit:
#     #         return False
#     if digit not in grid[col]:
#         return False
#     square_row = (row//3)*3
#     square_col = (col//3)*3
#     present = False
#     for i in range(0,3):
#         for j in range(0,3):
#             if grid[square_row+i][square_col+j] == digit:
#                 present = True
#                 #return False
#     #return True
#     return present

# def solve():
#     global grid,check
#     for row in range(9):
#         for col in range(9):
#             if check[row][col] == 0:
#                 for digit in range(1,10):
#                     if possible(row,col,digit):
#                         check[row][col] = digit
#                         grid[row][col] = digit
#                         solve()
#                         check[row][col] = 0  #Backtrack step
#                     pass
#                 return
#     #print('\nThe Solution')
#     printGrid()

tests = int(input())
rows = []
#print("tests"+tests)
for test in range(tests):
    for i in range(0,9):
        rows.append(input())
#print(len(rows))
grid = []
for row in rows:
    #sys.stdout.write(row.rstrip()+'\n')
    grid.append([int(char) for char in row.rstrip()])

# printGrid()
# print("Solution")

# check =[]
# for i in range(1,10):
#     check.append([0,0,0,0,0,0,0,0,0])
#solve()
pos = [ \
(0,0),\
(1,3),\
(2,6),\
(3,1),\
(4,4),\
(5,7),\
(6,2),\
(7,5),\
(8,8),\
]
for test in range(tests):
    for row,col in pos:
        _row = row+test*9
        _col = col
        if grid[_row][_col] + 1 == 10:
            grid[_row][_col] = 1
        else:
            grid[_row][_col] = grid[_row][_col] + 1

printGrid()
# for row in grid:
#     print(row)