Problem: 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](http://tiny.cc/636xmz).

The picture showing the correct sudoku solution:

<image>

Blocks are bordered with bold black color.

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

  * Any number in this field is in range [1; 9]; 
  * each row contains at least two equal elements; 
  * each column contains at least two equal elements; 
  * each 3 × 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 t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

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

Output

For each test case, print the answer — the initial field with at most 9 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


1
154873296
386592714
729641835
863725149
975314628
412968357
631457982
598236471
247189563


Output


154873396
336592714
729645835
863725145
979314628
412958357
631457992
998236471
247789563

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1 ? 100000000000000007 : 233333333333333333);
const int mod = (1 ? 1000000007 : 998244353);
const long long INF = 0x7fffffffffffffff;
const int inf = 0x7fffffff;
const double eps = 1e-9;
const int N = 1e6 + 5;
clock_t start, finish;
void time_in() { start = clock(); }
void time_out() {
  finish = clock();
  double tim = (double)(finish - start) / CLOCKS_PER_SEC;
  printf("Running time is %lf\n", tim);
}
inline long long mul(long long a, long long b) {
  long long s = 0;
  while (b) {
    if (b & 1) s = (s + a) % mod;
    a = (a << 1) % mod;
    b >>= 1;
  }
  return s % mod;
}
inline long long pow_mul(long long a, long long b) {
  long long s = 1;
  while (b) {
    if (b & 1) s = mul(s, a);
    a = mul(a, a);
    b >>= 1;
  }
  return s;
}
inline long long poww(long long a, long long b) {
  long long s = 1;
  while (b) {
    if (b & 1) s = (s * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return s % mod;
}
inline int read() {
  char c = getchar();
  int sgn = 1, ret = 0;
  while (c != '-' && (c < '0' || c > '9')) c = getchar();
  if (c == '-') sgn = -1, c = getchar();
  while (c >= '0' && c <= '9') ret = ret * 10 + c - 48, c = getchar();
  return ret * sgn;
}
void write(int x) {
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
inline long long phi(long long x) {
  long long ans = x;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans -= ans / i;
      while (x % i == 0) x /= i;
    }
  if (x > 1) ans -= ans / x;
  return ans;
}
int st[5][3] = {-1, 0, 0, 1, 0, 0, 0, -1, 0, 0, 1, 0, 0, 0, 1};
int t, cas;
int m, n;
string s[11];
int a[11][11];
int b[9][2] = {2, 2, 3, 6, 1, 7, 5, 3, 6, 5, 4, 9, 8, 1, 9, 4, 7, 8};
int main() {
  scanf("%d", &t);
  while (t--) {
    for (int i = 0; i < 9; i++) {
      cin >> s[i];
    }
    for (int i = 0; i < 9; i++) {
      for (int j = 0; j < 9; j++) {
        a[i + 1][j + 1] = s[i][j] - '0';
      }
    }
    int cnt = 0;
    for (int i = 0; i < 9; i++) {
      int x = b[i][0], y = b[i][1];
      for (int i = 1; i <= 9; i++) {
        if (a[x][y] != i) {
          a[x][y] = i;
          cnt++;
          break;
        }
      }
    }
    for (int i = 1; i <= 9; i++) {
      for (int j = 1; j <= 9; j++) {
        printf("%d", a[i][j]);
      }
      printf("\n");
    }
  }
}