> # include <iostream>
> # include <cstring>
> using namespace std;
> # define N 250000
> struct node
> {
> 	int row,col;
> 	int l,r,d,u;
> }buf[N];
> int ccc=324;
> int co=0,head=0,row,col,cn[1000];
> inline int posr(int a)
> {
> 	return 1+col+a;
> }
> inline int posc(int a)
> {
> 	return 1+a;
> }
> inline int block(int r,int c)
> {
> 	return r/3*3+c/3;
> }
> void init(int r,int c)
> {
> 	int i;
> 	row=r;
> 	col=c;
> 	buf[0].u=row+col;
> 	buf[0].l=col;
> 	buf[0].row=buf[0].col=-1;
> 	buf[0].r=1;
> 	buf[0].d=col+1;
> 	for(i=2;i<=col;i++)
> 		buf[i].l=i-1;
> 	for(i=1;i<col;i++)
> 		buf[i].r=i+1;
> 	for(i=1;i<=col;i++)
> 		buf[i].u=buf[i].d=i,buf[i].row=-1,buf[i].col=i-1;
> 	buf[col].r=0;
> 	buf[col+1].u=0;
> 	for(i=col+2;i<=col+row;i++)
> 		buf[i].u=i-1;
> 	for(i=col+1;i<col+row;i++)
> 		buf[i].d=i+1;
> 	for(i=col+1;i<=col+row;i++)
> 		buf[i].l=buf[i].r=i,buf[i].row=i-col-1,buf[i].col=-1;
> 	buf[row+col].d=0;
> 	co=row+col+1;
> 	memset(cn,0,sizeof(cn));
> }
> void insert(int r,int c)
> {
> 	buf[co].row=r;
> 	buf[co].col=c;
> 	buf[co].u=posc(c);
> 	buf[co].d=buf[posc(c)].d;
> 	buf[co].l=posr(r);
> 	buf[co].r=buf[posr(r)].r;
> 	buf[posc(c)].d=co;
> 	buf[buf[co].d].u=co;
> 	buf[posr(r)].r=co;
> 	buf[buf[co].r].l=co++;
> 	cn[c]++;
> }
> void remove(int c)
> {
> 	int i,j;
> 	buf[buf[posc(c)].l].r=buf[posc(c)].r;
> 	buf[buf[posc(c)].r].l=buf[posc(c)].l;
> 	ccc--;
> 	for(i=buf[posc(c)].d;i!=posc(c);i=buf[i].d)
> 	{
> 		for(j=buf[i].r;j!=i;j=buf[j].r)
> 		{
> 			buf[buf[j].u].d=buf[j].d;
> 			buf[buf[j].d].u=buf[j].u;
> 			if(buf[j].col!=-1)
> 				cn[buf[j].col]--;
> 		}
> 	}
> }
> void resume(int c)
> {
> 	int j,i;
> 	ccc++;
> 	for(i=buf[posc(c)].u;i!=posc(c);i=buf[i].u)
> 	{
> 		for(j=buf[i].l;j!=i;j=buf[j].l)
> 		{
> 			buf[buf[j].d].u=j;
> 			buf[buf[j].u].d=j;
> 			if(buf[j].col!=-1)
> 			    cn[buf[j].col]++;
> 		}
> 	}
> 	buf[buf[posc(c)].r].l=posc(c);
> 	buf[buf[posc(c)].l].r=posc(c);
> }
> int ans[100][2];
> char str[100];
> int dfs(int level)
> {
> 	if(buf[head].r==head)
> 	{
> 		for(int i=0;i<level;i++)
> 		{
> 		   str[ans[i][1]]=ans[i][0]%9+'1';
> 		}
> 		for(int i=0;i<81;i++)
> 		{
> 			cout<<str[i];
> 			if(i%9==8)
> 				cout<<endl;
> 			
> 		}
> 		return 1;
> 	}
> 	else
> 	{
> 		int maxnum=0xfffffff,pos,i,j;
> 		for(i=buf[head].r;i!=head;i=buf[i].r)
> 			if(cn[buf[i].col]<maxnum)
> 				maxnum=cn[buf[i].col],pos=buf[i].col;
> 
> 		remove(pos);
> 		for(i=buf[posc(pos)].d;i!=posc(pos);i=buf[i].d)
> 		{
> 			ans[level][0]=buf[i].row;
> 			if(pos<81) ans[level][1]=buf[i].col;
> 			for(j=buf[i].r;j!=i;j=buf[j].r)
> 				if(buf[j].col!=-1)
> 				{
> 				   remove(buf[j].col);
> 				   if(buf[j].col<81)
> 					   ans[level][1]=buf[j].col;
> 				}
> 		//	chk();
> 			if(dfs(level+1)) return 1;
> 			for(j=buf[i].l;j!=i;j=buf[j].l)
> 				if(buf[j].col!=-1)
> 					resume(buf[j].col);
> 		}
> 		resume(pos);
> 		return 0;
> 	}
> 
> 
> }
> int main()
> {	 
> 	 int testcase;
> 	 cin>>testcase;
> 	 while(testcase--)
> 	 {
>          char tmp[20];
> 		 str[0]='\0';
> 		 for(int i=0;i<9;i++)
> 		 {
> 			 cin>>tmp;
> 			 strcat(str,tmp);
> 		 }
> 		 init(729,324);
> 		 for(int i=0;i<9;i++)
> 		 {
> 			 for(int j=0;j<9;j++)
> 				 for(int k=0;k<9;k++)
> 				 {
> 					 insert(i*81+j*9+k,i*9+j);
> 					 insert(i*81+j*9+k,81+i*9+k);
> 					 insert(i*81+j*9+k,81+81+9*j+k);
> 					 insert(i*81+j*9+k,81+81+81+9*block(i,j)+k);
> 				 }
> 		 }
> 		 for(int i=0;i<9;i++)
> 			 for(int j=0;j<9;j++)
> 			   if(str[i*9+j]!='0')
> 			   {
> 				   remove(i*9+j);
> 				   int k;
> 				   for(k=buf[posc(i*9+j)].d;k!=posc(i*9+j)&&buf[k].row!=i*81+j*9+str[i*9+j]-'1';k=buf[k].d);
> 				   for(int l=buf[k].r;l!=k;l=buf[l].r)
> 						   if(buf[l].col!=-1)
> 							   remove(buf[l].col);					   
> 			   }
> 		dfs(0);
> 	 }
> 	return 0;
> }