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:
#qn given an arr of size n for every  i position find a min j such that j>i and arr[j]>arr[i]
#it prints the position of the nearest .
import sys
input = sys.stdin.readline
 #qn given an arr of size n for every  i position find a min j such that j>i and arr[j]>arr[i]
#it prints the position of the nearest .
# import sys
import heapq 
import copy
import math
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13

# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
'''############ ---- Input Functions ---- #######Start#####'''
def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

class Node:
    def _init_(self,val):
        self.data = val
        self.left = None
        self.right = None
##to initialize wire : object_name= node(val)##to create a new node
## can also be used to create linked list
class fen_tree:
    """Implementation of a Binary Indexed Tree (Fennwick Tree)"""
    
    #def __init__(self, list):
    #    """Initialize BIT with list in O(n*log(n))"""
    #    self.array = [0] * (len(list) + 1)
    #    for idx, val in enumerate(list):
    #        self.update(idx, val)

    def __init__(self, list):
        """"Initialize BIT with list in O(n)"""
        self.array = [0] + list
        for idx in range(1, len(self.array)):
            idx2 = idx + (idx & -idx)
            if idx2 < len(self.array):
                self.array[idx2] += self.array[idx]

    def prefix_query(self, idx):
        """Computes prefix sum of up to including the idx-th element"""
        # idx += 1
        result = 0
        while idx:
            result += self.array[idx]
            idx -= idx & -idx
        return result
    def prints(self):
        print(self.array)
        return
        # for i in self.array:
        #     print(i,end = " ")
        # return 
    def range_query(self, from_idx, to_idx):
        """Computes the range sum between two indices (both inclusive)"""
        return self.prefix_query(to_idx) - self.prefix_query(from_idx - 1)

    def update(self, idx, add):
        """Add a value to the idx-th element"""
        # idx += 1
        while idx < len(self.array):
            self.array[idx] += add
            idx += idx & -idx


def pre_sum(arr):
	#"""returns the prefix sum inclusive ie ith position in ans  represent sum from 0 to ith position"""
	p = [0]
	for i in arr:
		p.append(p[-1] + i)
	p.pop(0)
	return p

def pre_back(arr):
	#"""returns the prefix sum inclusive ie ith position in ans  represent sum from 0 to ith position"""
	p = [0]
	for i in arr:
		p.append(p[-1] + i)
	p.pop(0)
	return p
def bin_search(arr,l,r,val):#strickly greater
	if arr[r] <= val:
		return r+1	
	if r-l < 2:
		if arr[l]>val:
			return l
		else:
			return r
	mid = int((l+r)/2)
	if arr[mid] <= val:
		return bin_search(arr,mid,r,val)
	else:
		return bin_search(arr,l,mid,val)
def search_leftmost(arr,val):
	def helper(arr,l,r,val):
		# print(arr)
		print(l,r)
		if arr[l] == val:
			return l
		if r -l <=1:
			if arr[r] == val:
				return r
			else:
				print("not found")
				return
		mid = int((r+l)/2)
		if arr[mid] >= val:
			return helper(arr,l,mid,val)
		else:
			return helper(arr,mid,r,val)
	return helper(arr,0,len(arr)-1,val)
def search_rightmost(arr,val):
	def helper(arr,l,r,val):
		# print(arr)
		print(l,r)
		if arr[r] == val:
			return r
		if r -l <=1:
			if arr[l] == val:
				return r
			else:
				print("not found")
				return
		mid = int((r+l)/2)
		if arr[mid] > val:
			return helper(arr,l,mid,val)
		else:
			return helper(arr,mid,r,val)
	return helper(arr,0,len(arr)-1,val)


def pr_list(a):
	print(*a, sep=" ")
def main():
	tests =  inp()
	# tests = 1
	mod = 1000000007
	limit = 10**18
	# print(limit)

	for test in range(tests):
		s = [[] for i in range(9) ]
		for i in range(9):
			s[i] = insr()
		# print("taken")
		change = [[0,0],[1,7],[2,5],[3,6],[4,4],[5,1],[6,2],[7,8],[8,3]]
		for i in change:
			s[i[0]][i[1]] = str( (int(s[i[0]][i[1]]) -2 +9)%9 +1)
		for i in range(9):
			s[i] = "".join(s[i])
			print(s[i])

		# # for i in range()
		# for i in range(1,10):
		# 	print((i-2)%9 +1)

				
			
		




if __name__== "__main__":
  main()