1#include<iostream>
  2#include<cstdlib>
  3#include<string>
  4using namespace std;
  5int map[10][10];
  6int row[10][10];
  7int col[10][10];
  8int grid[10][10];
  9void input()
 10{
 11 // char a[10];
 12  string a;
 13  for(int i=0;i<9;i++)
 14  {
 15    //getline(cin,a);
 16    cin>>a;
 17    for(int j=0;j<9;j++)
 18    {
 19      map[i][j]=a[j]-'0';
 20      if(map[i][j])
 21      {
 22        int k=3*(i/3)+j/3;
 23        row[i][map[i][j]]=1;   //indicates this row has the number map[i][j]
 24        col[j][map[i][j]]=1;   //
 25        grid[k][map[i][j]]=1;
 26      }
 27    }
 28  }
 29}
 30int dfs(int i,int j)
 31{
 32    int flag=0;
 33    if(i==9)
 34     return 1;
 35    if(map[i][j])
 36    {
 37      if(j==8)
 38       flag=dfs(i+1,0);
 39      else
 40       flag=dfs(i,j+1);
 41     if(flag)
 42       return 1;
 43     else
 44       return 0;  //这里不要改变map的值，起得是一个传递的作用 
 45    }//在这里如果当前要保存当前递归的信息，如果结果不满足，那么就要回朔，所以设置flag保存此次递归的结果是否可行
 46    else
 47    {
 48      int k=3*(i/3)+j/3;
 49      for(int m=1;m<=9;m++)
 50       {
 51         
 52         if(!row[i][m]&&!col[j][m]&&!grid[k][m])
 53         {
 54           map[i][j]=m;
 55           row[i][m]=1;
 56           col[j][m]=1;
 57           grid[k][m]=1;
 58           if(j==8)
 59            flag=dfs(i+1,0);
 60           else
 61            flag=dfs(i,j+1); 
 62           //如果将}放在这里结束if的话，那么就是错误的答案，因为回朔要紧接着上一次递归进去的位置，这个位置很重要，否则就是错误的答案 
 63           //在这里如果当前要保存当前递归的信息，如果结果不满足，那么就要回朔，所以设置flag保存此次递归的结果是否可行 
 64        if(flag)
 65         return 1;
 66        else  //进行回朔 
 67        {
 68          map[i][j]=0;
 69          row[i][m]=0;
 70          col[j][m]=0;
 71          grid[k][m]=0; 
 72        }
 73       }//if
 74      }//for
 75    }
 76  return 0; 
 77}
 78void output()
 79{
 80  for(int i=0;i<9;i++)
 81  { for(int j=0;j<9;j++)
 82    {
 83      cout<<map[i][j];
 84    }
 85   cout<<endl;
 86  }
 87}
 88int main()
 89{
 90    int T;
 91    cin>>T;
 92    while(T--)
 93    {
 94    memset(row,0,sizeof(row));
 95    memset(grid,0,sizeof(grid));
 96    memset(col,0,sizeof(col));
 97    input();
 98    dfs(0,0);
 99    output();
100    }
101    system("pause");
102} 
103