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;
inline long long max3(long long a, long long b, long long c) {
  return (a) > (b) ? ((a) > (c) ? (a) : (c)) : ((b) > (c) ? (b) : (c));
}
inline long long min3(long long a, long long b, long long c) {
  return (a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c));
}
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
inline long long mod(long long a, long long m) { return (a % m + m) % m; }
long long modinv(long long a) {
  long long x, y;
  extgcd(a, 1000000007, x, y);
  return mod(x, 1000000007);
}
long long gcd(long long u, long long v) {
  long long r;
  while (0 != v) {
    r = u % v;
    u = v;
    v = r;
  }
  return u;
}
long long lcm(long long u, long long v) { return u / gcd(u, v) * v; }
void get_all_factors(int a[], long long int n) {
  long long int w = sqrt(n);
  for (int i = 1; i <= w; i++) {
    if (n % i == 0) {
      a[i]++;
      a[n / i]++;
    }
  }
  long long int x = ceil(sqrt(n));
  if (sqrt(n) == ceil(sqrt(n))) a[(int)sqrt(n)]--;
}
long long int memo[100000][110] = {0};
long long C(long long n, long long r) {
  if (r == 0 || r == n) return 1;
  if (memo[n][r] != -1) return memo[n][r];
  return memo[n][r] =
             (C(n - 1, r - 1) % 1000000007 + C(n - 1, r) % 1000000007) %
             1000000007;
}
int valid(string s, int i) {
  if (s == "lol" or i == -1000050000) {
    return 0;
  }
  return 1;
}
void status(string s1 = "lol", long long int i1 = -1000050000,
            string s2 = "lol", long long int i2 = -1000050000,
            string s3 = "lol", long long int i3 = -1000050000) {
  if (1) {
    if (valid(s1, i1)) {
      cout << s1 << "=" << i1 << "  ";
    }
    if (valid(s2, i2)) {
      cout << s2 << "=" << i2 << "  ";
    }
    if (valid(s3, i3)) {
      cout << s3 << "=" << i3 << "  ";
    }
    cout << endl;
  }
}
long long int poww(long long b, long long e) {
  if (e == 0)
    return 1;
  else if (e % 2 == 0) {
    long long a = pow(b, e / 2);
    return a * a;
  } else {
    long long a = pow(b, e / 2);
    return b * a * a;
  }
}
long long int powm(long long x, long long y, long long m = 1000000007) {
  x = x % m;
  long long res = 1;
  while (y) {
    if (y & 1) res = res * x;
    res %= m;
    y = y >> 1;
    x = x * x;
    x %= m;
  }
  return res;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n = 9;
    char a[9][9];
    map<pair<int, int>, int> row, col;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        cin >> a[i][j];
      }
    }
    int actual[9] = {0};
    int cnt = 0;
    int f = 0;
    int j = 0;
    for (int i = 0; i < n; i++) {
      if (cnt == 3) {
        cnt = 0;
        f++;
        j = f;
      }
      int old = a[i][j] - 48;
      int nn = (old + 1) % 10;
      if (nn == 0) {
        nn = 1;
      }
      a[i][j] = char(48 + nn);
      cnt++;
      j += 3;
    }
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        cout << a[i][j];
      }
      cout << endl;
    }
  }
}