Faith

#include<stdio.h>
#include<string.h>
char s[11][11];
bool ok=false;
int check(int n,int num)
{
	int i,j,x,y;
	for(i=0,j=n/9;i<9;i++)
	{
		if(s[j][i]==num)
			return 0;
	}
	for(i=0,j=n%9;i<9;i++)
	{
		if(s[i][j]==num)
			return 0;
	}
	x=n/9/3*3+3;
	y=n%9/3*3+3;
	for(i=n/9/3*3;i<x;i++)
	{
		for(j=n%9/3*3;j<y;j++)
		{
			if(s[i][j]==num)
				return 0;
		}
	}
	return 1;
}
int dfs(int n)
{
	int i;
	if(n<0)
	{
		ok=true;
		return 0;
	}
	if(s[n/9][n%9]!=0)
		dfs(n-1);
	else
	{
		for(i=1;i<=9;i++)
		{
				if(check(n,i)==1)
				{
					s[n/9][n%9]=i;
					dfs(n-1);
					if(ok)
						return 0;
					s[n/9][n%9]=0;
				}
		}
	}
	return 0;
}
int main()
{
	freopen("2.txt","r",stdin);
	int n,i,j,k;
	scanf("%d ",&n);
	while(n--)
	{
		memset(s,0,sizeof(s));
		ok=false;
		for(i=0;i<9;i++)
			scanf("%s",s[i]);
		for(i=0;i<9;i++)
		{
			for(j=0;j<9;j++)
			{
				s[i][j]-='0';
			}
		}
		dfs(80);
		for(i=0;i<9;i++)
		{
			for(j=0;j<9;j++)
			{
				printf("%d",s[i][j]);
			}
			printf("\n");
		}
 
 
	}
	return 0;
}