1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <queue>
  9 #include <set>
 10 using namespace std;
 11 
 12 #define ll long long
 13 #define eps 1e-8
 14 #define mod 21092013
 15 
 16 #define inf 0x3f3f3f3f
 17 #define maxr 777
 18 #define maxn (maxr*maxr)
 19 int n,m;
 20 int L[maxn],R[maxn],U[maxn],D[maxn],cnt;
 21 int row[maxn],col[maxn];
 22 int N[maxr],use[maxr],head[maxr];
 23 void init(){
 24     memset(head,-1,sizeof(head));
 25     memset(N,0,sizeof(N));
 26     for(int i=0;i<=m;++i){
 27         L[i]=i-1,R[i]=i+1;
 28         U[i]=D[i]=i;
 29         row[i]=0,col[i]=i;
 30     }
 31     L[0]=m,R[m]=0;
 32     cnt=m;
 33 }
 34 void remove(int c){// 删除列以及所在列含有1的行
 35     L[R[c]]=L[c],R[L[c]]=R[c];
 36     for(int i=D[c];i!=c;i=D[i])
 37         for(int j=R[i];j!=i;j=R[j])
 38             U[D[j]]=U[j],D[U[j]]=D[j],--N[col[j]];
 39 }
 40 void resume(int c){// 恢复列以及所在列含有1的行
 41     for(int i=U[c];i!=c;i=U[i])
 42         for(int j=L[i];j!=i;j=L[j])
 43             U[D[j]]=D[U[j]]=j,++N[col[j]];
 44     L[R[c]]=R[L[c]]=c;
 45 }
 46 int low(){
 47     int mi=maxr,idx=0;
 48     for(int i=R[0];i;i=R[i])if(N[i]<mi&&N[i])mi=N[i],idx=i;
 49     return idx;
 50 }
 51 void link(int r,int c){
 52     ++N[c],++cnt;
 53     row[cnt]=r,col[cnt]=c;
 54     U[cnt]=U[c],D[cnt]=c;
 55     U[D[cnt]]=D[U[cnt]]=cnt;
 56     if(head[r]==-1)
 57         head[r]=L[cnt]=R[cnt]=cnt;
 58     else {
 59         L[cnt]=L[head[r]];
 60         R[cnt]=head[r];
 61         L[R[cnt]]=R[L[cnt]]=cnt;
 62     }
 63 }
 64 int xy[maxr][2];char num[maxr];
 65 char ch[12][12];
 66 bool dance(int dep){
 67     if(R[0]==0)return true;
 68     int c=low();
 69     if(c==0)return false;
 70     for(int i=D[c];i!=c;i=D[i]){
 71         int r=row[i];
 72         ch[xy[r][0]][xy[r][1]]=num[r];
 73         use[dep]=i;
 74         remove(col[i]);
 75         for(int j=R[i];j!=i;j=R[j])remove(col[j]);
 76         if(dance(dep+1))return true;
 77         for(int j=L[i];j!=i;j=L[j])resume(col[j]);
 78         resume(col[i]);
 79     }
 80     return false;
 81 }
 82 
 83 int main(){
 84     int t,ca=0;
 85     scanf("%d",&t);
 86     while(t--){
 87         if(ca)scanf("%s",ch[0]);
 88         if(ca)puts("---");
 89         ca=1;
 90         n=0,m=324;
 91         init();
 92         for(int i=1;i<=9;++i)scanf("%s",ch[i]+1);
 93         for(int i=1;i<=9;++i){
 94             for(int j=1;j<=9;++j){
 95                 if(ch[i][j]>=‘0‘&&ch[i][j]<=‘9‘){
 96                     int val=ch[i][j]-‘0‘;
 97                     ++n;
 98                     link(n,(i-1)*9+val);
 99                     link(n,81+(j-1)*9+val);
100                     link(n,162+(i-1)*9+j);
101                     link(n,243+((i-1)/3*3+(j+2)/3-1)*9+val );
102                     xy[n][0]=i,xy[n][1]=j;
103                     num[n]=val+‘0‘;
104                 }
105                 else {
106                     for(int k=1;k<=9;++k){
107                         int val=k;
108                         ++n;
109                         link(n,(i-1)*9+val);
110                         link(n,81+(j-1)*9+val);
111                         link(n,162+(i-1)*9+j);
112                         link(n,243+((i-1)/3*3+(j+2)/3-1)*9+val );
113                         xy[n][0]=i,xy[n][1]=j;
114                         num[n]=val+‘0‘;
115                     }
116                 }
117             }
118         }
119         if(dance(0))for(int i=1;i<=9;++i)printf("%s\n",ch[i]+1);
120         else puts("impossible");
121     }
122     return 0;
123 }