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 
# sys.stdin = open('input.txt', 'r') 
# sys.stdout = open('output.txt', 'w')
# import re 
gg="abcdefghijklmnopqrstuvwxyz"
# def negmod(a, m): 
#     return (a%m + m) % m 
# for C in range(int(input())):
# rawstr = ''.join([int(x) * '(' + x + ')' * int(x) for x in str(input())])
# for _ in range(9):
# rawstr = rawstr.replace(')(', '')
# print("Case #{}: {}".format(C+1, rawstr))
# def f(n):
# 	if(n<=1):
# 		return 1
# 	elif(n==2):
# 		return 2
# 	else:
# 		return((f(n-1)*2)-1)
t=int(input())
while(t):
	t-=1
	l=[]
	ans=[]
	for x in range(0,9):
		s=str(input())
		l.append(s)
	for x in l:
		a=[]
		for letter in x:
			if(letter=='1'):
				a.append('2')
			else:
				a.append(letter)
			# print(letter,end=" ")
		ans.append(a)
	for x in range(0,9):
		for y in range(0,9):
			print(ans[x][y],end="")
		print()
	print()
	# n,a,b=map(int,input().split())
	# b=min(a,b)
	# r=(a%b)
	# s=gg[:b]*(a//b) + gg[:r]
	# # print(gg[b:a])
	# ans=""
	# ans=s[:]
	# for i in range(0,n-a):
	# 	ans+=s[i%b]
	# print(ans)
	# print(f(2*(n-1)))
	# ans=0
	# l=list(map(int,input().split()))
	# l.sort()
	# print(l)
	# if(n%2==0):
	# 	i=n//2
	# 	j=i-1
	# 	while(j>=0 and i<n):
	# 		print(l[j],end=" ")
	# 		print(l[i],end=" ")
	# 		j-=1
	# 		i+=1
	# else:
	# 	i=(n//2)+1
	# 	j=i-1
	# 	while(j>=1 and i<n):
	# 		print(l[j],end=" ")
	# 		print(l[i],end=" ")
	# 		i+=1
	# 		j-=1
	# 	print(l[0],end=" ")
	# print()
	# if(n<=1):
	# 	print(1)
	# elif(n==2):
	# 	print(2)
	# else:
	# 	ans=2
	# 	for i in range (1,n-1):
	# 		ans=(ans*2)-1
	# 	print(ans)

# 	l=[]
# 	regrex=""
# 	for i in range(0,n):
# 		l.append(str(input()))
# 		regrex+=l[i]
# 	# print(l,regrex,end=" ")
# 	for i in range(0,len(l)):
# 		match = re.match(regrex,l[i])
# 		print(match)
# def get(now,distance):
# 	if(now==distance):
# 		return (now+distance)
# 	elif(now - distance>0):
# 		return (now- distance)
# 	else:
# 		return(now+ distance)
# n,k,s=map(int,input().split())
# if((n-1)*k < s or k>s):
# 	print("NO")
# else:
# 	print("YES")
# 	l=[]
# 	l.append(1)
# 	td=0
# 	dif=(s-td)
# 	while(k>0):
# 		walk=min(n-1,dif-k+1)
# 		p=get(l[-1],walk)
# 		# print(l[-1],p)
# 		l.append(p)
# 		k-=1
# 		dif-=walk
# 	for i in range (1,len(l)):
# 		print(l[i],end=" ")
# # l=[1,2,3,4,5]
# # print(l[1:-1])



# sort(v.begin(), v.end(), comp);
# if(n% 2 == 0){
#     int y = n/2;
#     int x = y -1;
#     for(; x>=0 && y<n; x--, y++){
#         cout<<v[x]<<" "<<v[y]<<" ";
#     }
# }else{
#     int z = v[0];
#     n--;
#     int x = n/2;
#     int y = x + 1;  
#     for(; x>0 && y<n+1; x--, y++){
#         cout<<v[x]<<" "<<v[y]<<" ";
#     }
#     cout<<z;