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:
def givalt(ch):
	if(int(ch)+1<9):
		return str(int(ch)+1)
	return str(1)

def help():
	inp=input()
	changed=givalt(inp[0])+inp[1:]
	print(changed)
	inp=input()
	changed=inp[:3]+givalt(inp[3])+inp[3+1:]
	print(changed)
	inp=input()
	changed=inp[:6]+givalt(inp[6])+inp[6+1:]
	print(changed)
	inp=input()
	changed=inp[:1]+givalt(inp[1])+inp[1+1:]
	print(changed)
	inp=input()
	changed=inp[:4]+givalt(inp[4])+inp[4+1:]
	print(changed)
	inp=input()
	changed=inp[:7]+givalt(inp[7])+inp[7+1:]
	print(changed)
	inp=input()
	changed=inp[:2]+givalt(inp[2])+inp[2+1:]
	print(changed)
	inp=input()
	changed=inp[:5]+givalt(inp[5])+inp[5+1:]
	print(changed)
	inp=input()
	changed=inp[:8]+givalt(inp[8])
	print(changed)


for qw in range(int(input())):
	help()




	# n,k=map(int,inf.readline().split(" "))
	# ans=['a']*(n)
	# currpos=n-1
	# while k!=1:
	# 	if(k>)
		


# for i in dicti:
# 	temp=0
# 	for j in helper:
# 		if(j[0]<=i[0] and j[1]<=i[1]):
# 			temp+=(i[0]-j[0]+1)*(i[1]-j[1]+1)
# 		if(j[1]<=i[0] and j[0]<=i[1] and j[0]!=j[1]):
# 			temp+=(i[0]-j[1]+1)*(i[1]-j[0]+1)
# 	count+=temp*dicti[i]



# def all_partitions(string):
#     for cutpoints in range(1 << (len(string)-1)):
#         result = []
#         lastcut = 0
#         for i in range(len(string)-1):
#             if (1<<i) & cutpoints != 0:
#                 result.append(string[lastcut:(i+1)])
#                 lastcut = i+1
#         result.append(string[lastcut:])
#         yield result

# maxyet=0
# store={'h': -6, 'e': -7, 'l': -8, 'o': 3, 'he': 3, 'hel': -3, 'el': 0, 'hell': 6, 'ell': -5, 'll': 10, 'hello': -3, 'ello': -8, 'llo': 9, 'lo': -6}

# def quality(stri):
# 	return store[stri]

# for partition in all_partitions("hel"):
#     temp=0
#     for i in partition:
#     	temp+=quality(i)
#     if(temp>maxyet):
#     	print(partition)
#     	maxyet=temp

# print(maxyet)