D. Anti-Sudoku_牛客博客

链接：https://codeforces.ml/contest/1335/problem/D

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.

The picture showing the correct sudoku solution:

正在上传…重新上传取消

Blocks are bordered with bold black color.

Your task is to change at most 99 elements of this field (i.e. choose some 1≤i,j≤91≤i,j≤9 and change the number at the position (i,j)(i,j) to any other number in range [1;9][1;9]) to make it anti-sudoku. The anti-sudoku is the 9×99×9 field, in which:

Any number in this field is in range [1;9][1;9];
each row contains at least two equal elements;
each column contains at least two equal elements;
each 3×33×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 tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.

Each test case consists of 99 lines, each line consists of 99 characters from 11 to 99 without any whitespaces — the correct solution of the sudoku puzzle.

Output

For each test case, print the answer — the initial field with at most 99 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

Copy

output

Copy

代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,r,l,k,max1,s;
long long a[15][15];
char x;
long long b[10],c[10];
int main()
{
	cin>>t;
	while(t--)
	{
		for(int i=1;i<=9;i++)
		{
			//b[i]=0;
			//c[i]=0;
			for(int j=1;j<=9;j++)
			{
				cin>>x;
				a[i][j]=x-'0'; 
			}
		}
		if(a[1][1]==1)
		a[1][1]=2;
		else
		a[1][1]=1;
		if(a[2][4]==1)
		a[2][4]=2;
		else
		a[2][4]=1;
		if(a[3][7]==1)
		a[3][7]=2;
		else
		a[3][7]=1;
		if(a[4][2]==1)
		a[4][2]=2;
		else
		a[4][2]=1;
		if(a[5][5]==1)
		a[5][5]=2;
		else
		a[5][5]=1;
		if(a[6][8]==1)
		a[6][8]=2;
		else
		a[6][8]=1;
		if(a[7][3]==1)
		a[7][3]=2;
		else
		a[7][3]=1;
		if(a[8][6]==1)
		a[8][6]=2;
		else
		a[8][6]=1;
		if(a[9][9]==1)
		a[9][9]=2;
		else
		a[9][9]=1;
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				cout<<a[i][j];
			}
			cout<<endl;
		}
	}
}