#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int A[10][10]; int row[10][15]; int col[10][15]; int num[10][15]; int tot; struct abc { int x,y; int g; }node[90]; int flag; char s[10][10]; void DFS(int x) { int i; if(x==tot) { flag=1; return; } for(i=1;i<=9;i++) { if(row[node[x].x][i]==0) { if(col[node[x].y][i]==0) { if(num[node[x].g][i]==0) { row[node[x].x][i]=1; col[node[x].y][i]=1; num[node[x].g][i]=1; A[node[x].x][node[x].y]=i; DFS(x+1); if(flag==1) return; row[node[x].x][i]=0; col[node[x].y][i]=0; num[node[x].g][i]=0; } } } } } int main() { int T; scanf("%d",&T); while(T--) { int i,j; for(i=0;i<9;i++) scanf("%s",s[i]); for(i=1;i<=9;i++) for(j=1;j<=9;j++) A[i][j]=s[i-1][j-1]-'0'; memset(row,0,sizeof(row)); memset(col,0,sizeof(col)); memset(num,0,sizeof(num)); tot=0;flag=0; for(i=1;i<=9;i++) for(j=1;j<=9;j++) { if(A[i][j]==0) { node[tot].x=i; node[tot].y=j; if(i>=1&&i<=3) { if(j>=1&&j<=3) node[tot].g=1; if(j>=4&&j<=6) node[tot].g=2; if(j>=7&&j<=9) node[tot].g=3; } if(i>=4&&i<=6) { if(j>=1&&j<=3) node[tot].g=4; if(j>=4&&j<=6) node[tot].g=5; if(j>=7&&j<=9) node[tot].g=6; } if(i>=7&&i<=9) { if(j>=1&&j<=3) node[tot].g=7; if(j>=4&&j<=6) node[tot].g=8; if(j>=7&&j<=9) node[tot].g=9; } tot++; } } int g; for(i=1;i<=9;i++) { for(j=1;j<=9;j++) { if(A[i][j]!=0) row[i][A[i][j]]=1,col[j][A[i][j]]=1; if(i>=1&&i<=3) { if(j>=1&&j<=3) g=1; if(j>=4&&j<=6) g=2; if(j>=7&&j<=9) g=3; } if(i>=4&&i<=6) { if(j>=1&&j<=3) g=4; if(j>=4&&j<=6) g=5; if(j>=7&&j<=9) g=6; } if(i>=7&&i<=9) { if(j>=1&&j<=3) g=7; if(j>=4&&j<=6) g=8; if(j>=7&&j<=9) g=9; } num[g][A[i][j]]=1; } } DFS(0); for(i=1;i<=9;i++) { for(j=1;j<=9;j++) { printf("%d",A[i][j]); } printf(" "); } } return 0; }