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 LL = long long;
using ULL = unsigned long long;
using LLL = __int128;
using ULLL = unsigned __int128;
namespace std {
void swap(int& x, int& y) { x ^= y ^= x ^= y; }
void swap(LL& x, LL& y) { x ^= y ^= x ^= y; }
};  // namespace std
using std::swap;
template <typename T, typename P>
auto max(const T& x, const P& y) -> decltype(x < y ? y : x) {
  return x < y ? y : x;
}
template <typename T, typename P>
auto min(const T& x, const P& y) -> decltype(x < y ? x : y) {
  return x < y ? x : y;
}
template <typename T, typename... Args>
auto max(const T& x, const Args&... args) -> decltype(max(x, max(args...))) {
  return max(x, max(args...));
}
template <typename T, typename... Args>
auto min(const T& x, const Args&... args) -> decltype(min(x, min(args...))) {
  return min(x, min(args...));
}
template <typename T>
T max(const T& x) {
  return x;
}
template <typename T>
T min(const T& x) {
  return x;
}
class IO {
  static const int MAXSIZE = 1 << 20;
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
  long double eps = 1e-8L;
  LLL pow10 = 1000000;
  int precision;
  FILE *infile, *outfile;

 public:
  IO(FILE* in = nullptr, FILE* out = nullptr)
      : precision(6), infile(in), outfile(out) {
    p1 = p2 = buf;
    pp = pbuf;
  }
  ~IO() { fwrite(pbuf, 1, pp - pbuf, outfile); }
  inline static bool blank(char ch);
  inline void flush();
  inline void input(const char* str);
  inline void output(const char* str);
  inline void input(FILE* f);
  inline void output(FILE* f);
  inline int getch();
  template <typename T, typename... Args>
  bool read(T& x, Args&... args);
  inline bool read();
  template <typename T>
  typename std::enable_if<
      std::is_integral<T>::value || std::is_floating_point<T>::value ||
          std::is_same<T, LLL>::value || std::is_same<T, ULLL>::value,
      bool>::type
  read(T& x);
  bool read(char& ch);
  bool read(char* s);
  bool readline(char* s);
  inline void putch(const char c);
  inline void putback(const char c);
  inline void setprecision(int n = 6);
  template <typename T, typename... Args>
  void write(const T& x, const Args&... args);
  inline void write();
  template <typename T>
  typename std::enable_if<std::is_integral<T>::value ||
                              std::is_same<T, LLL>::value ||
                              std::is_same<T, ULLL>::value,
                          void>::type
  write(T x);
  inline void write(char c);
  template <typename T>
  typename std::enable_if<std::is_floating_point<T>::value, void>::type write(
      T x);
  inline void write(bool x);
  void write(char* s);
  void write(const char* s);
  template <typename... Args>
  void writeln(Args... x) {
    write(x...), putch('\n');
  }
} io(stdin, stdout), err(nullptr, stderr);
template <typename... Args>
inline void writeln(Args... x) {
  io.write(x...), io.putch('\n');
}
const int maxn = 10;
const unsigned short d[][2] = {{},     {1, 1}, {2, 4}, {3, 7}, {4, 2},
                               {5, 5}, {6, 8}, {7, 3}, {8, 6}, {9, 9}};
unsigned short A[maxn][maxn], ans[maxn][maxn];
bool vis[maxn];
int main() {
  int q;
  io.read(q);
  while (q--) {
    for (int i = 1; i <= 9; i++)
      for (int j = 1; j <= 9; j++) {
        char ch;
        io.read(ch);
        ans[i][j] = A[i][j] = ch ^ 48;
      }
    for (int _ = 1; _ <= 9; _++) {
      int i = d[_][0], j = d[_][1];
      for (int k = 1; k <= 9; k++)
        if (k != A[i][j]) {
          ans[i][j] = k;
          break;
        }
    }
    for (int i = 1; i <= 9; i++, writeln())
      for (int j = 1; j <= 9; j++) io.putch(ans[i][j] ^ 48);
  }
  return 0;
}
inline bool IO::blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void IO::flush() {
  fwrite(pbuf, 1, pp - pbuf, outfile), pp = pbuf;
  fflush(outfile);
}
inline void IO::input(const char* str) {
  FILE* file = fopen(str, "rb");
  infile = file;
}
inline void IO::output(const char* str) {
  FILE* file = fopen(str, "wb");
  outfile = file;
}
inline void IO::input(FILE* f) { infile = f; }
inline void IO::output(FILE* f) { outfile = f; }
inline int IO::getch() {
  return (p1 == p2 ? (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, infile)) : 0),
         (p1 == p2) ? EOF : *p1++;
}
inline void IO::putback(const char c) { *(--p1) = c; }
template <typename T, typename... Args>
bool IO::read(T& x, Args&... args) {
  return read(x) && read(args...);
}
inline bool IO::read() { return true; }
template <typename T>
typename std::enable_if<
    std::is_integral<T>::value || std::is_floating_point<T>::value ||
        std::is_same<T, LLL>::value || std::is_same<T, ULLL>::value,
    bool>::type
IO::read(T& x) {
  T tmp = 1;
  bool sign = false;
  x = 0;
  int ch = getch();
  for (; !(ch >= '0' && ch <= '9') && ~ch; ch = getch())
    if (ch == '-') sign = true;
  if (!(~ch)) return false;
  for (; (ch >= '0' && ch <= '9'); ch = getch()) x = x * 10 + (ch - '0');
  if (ch == '.' && std::is_floating_point<T>::value)
    for (ch = getch(); (ch >= '0' && ch <= '9'); ch = getch())
      tmp /= 10.0, x += tmp * (ch - '0');
  if (~ch) putback(ch);
  if (sign) x = -x;
  return true;
}
bool IO::read(char& ch) {
  for (ch = getch(); blank(ch) && ~ch; ch = getch())
    ;
  return ~ch;
}
bool IO::read(char* s) {
  int ch = getch();
  while (blank(ch)) ch = getch();
  if (!(~ch)) return false;
  while (!blank(ch) && ~ch) *s++ = ch, ch = getch();
  *s = 0;
  if (~ch) putback(ch);
  return true;
}
bool IO::readline(char* s) {
  int ch = getch();
  while (blank(ch) && ch != '\n') ch = getch();
  if (!(~ch)) return false;
  while (ch != '\n' && ~ch) *s++ = ch, ch = getch();
  *s = 0;
  if (~ch) putback(ch);
  return true;
}
inline void IO::putch(const char c) {
  ((pp - pbuf == MAXSIZE) ? fwrite(pbuf, 1, MAXSIZE, outfile), pp = pbuf : 0),
      *pp++ = c;
}
inline void IO::setprecision(int n) {
  precision = n;
  eps = powl(10.0L, -precision - 2);
  pow10 = powl(10.0L, precision) + eps;
}
template <typename T, typename... Args>
void IO::write(const T& x, const Args&... args) {
  write(x);
  write(args...);
}
inline void IO::write() {}
template <typename T>
typename std::enable_if<std::is_integral<T>::value ||
                            std::is_same<T, LLL>::value ||
                            std::is_same<T, ULLL>::value,
                        void>::type
IO::write(T x) {
  if (x < 0) x = ~x + 1, putch('-');
  static T sta[100];
  int top = 0;
  do sta[top++] = x % 10, x /= 10;
  while (x);
  while (top) putch(sta[--top] + '0');
}
inline void IO::write(bool x) { putch(x ^ 48); }
inline void IO::write(char c) { putch(c); }
template <typename T>
typename std::enable_if<std::is_floating_point<T>::value>::type IO::write(T x) {
  if (x == 0) {
    putch('0'), putch('.');
    for (int i = 1; i <= precision; i++) putch('0');
    return;
  }
  if (x < 0) putch('-'), x = -x;
  T res = (LLL)(x * pow10 + 0.5) / (pow10 * 1.0);
  LLL y = LLL(res * pow10 + eps) % pow10;
  write(LLL(res + eps));
  if (precision) {
    putch('.');
    static int sta[100], p = 0;
    for (; p < precision; y /= 10) sta[++p] = y % 10;
    for (int i = p; i >= 1; i--) putch(sta[i] ^ 48);
  }
}
void IO::write(char* s) {
  while (*s) putch(*s++);
}
void IO::write(const char* s) {
  while (*s) putch(*s++);
}