D. Anti-Sudoku

D. Anti-Sudoku

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a correct solution of the sudoku puzzle. If you don't know what is the sudoku, you can read about it here.

The picture showing the correct sudoku solution:

正在上传…重新上传取消

Blocks are bordered with bold black color.

Your task is to change at most 99 elements of this field (i.e. choose some 1≤i,j≤91≤i,j≤9 and change the number at the position (i,j)(i,j) to any other number in range [1;9][1;9]) to make it anti-sudoku. The anti-sudoku is the 9×99×9 field, in which:

• Any number in this field is in range [1;9][1;9];
• each row contains at least two equal elements;
• each column contains at least two equal elements;
• each 3×33×3 block (you can read what is the block in the link above) contains at least two equal elements.

It is guaranteed that the answer exists.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.

Each test case consists of 99 lines, each line consists of 99 characters from 11 to 99 without any whitespaces — the correct solution of the sudoku puzzle.

Output

For each test case, print the answer — the initial field with at most 99 changed elements so that the obtained field is anti-sudoku. If there are several solutions, you can print any. It is guaranteed that the answer exists.

Example

input

Copy

1
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563

output

Copy

154873396
336592714
729645835
863725145
979314628
412958357
631457992
998236471
247789563

=========================================================================

脑筋急转弯，不过要先知道数独的定义，也就是每个粗9格里面是1-9无重复，每行1-9无重复，每列1-9无重复

那么也就是说每行一个1，一个2，每列一个1，一个2，每个粗9格一个1，一个2，然后整个八十一格9个1,9个2，我们只需要把1改成2，那么每行两个2，每列两个2，每个粗9格两个2

脑筋急转弯

# include
 
using namespace std;
char s[100][100];
 
int main ()
{
 
    int t;
 
    cin>>t;
 
    while(t--)
    {
        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++)
            {
               cin>>s[i][j];
            }
 
        }
 
        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++)
            {
                if(s[i][j]=='1')
                    cout<<'2';
                else
                    cout<<s[i][j];
            }
 
            cout<
 
        }
    }
    return 0;
 
}