#include <iostream>#include <sstream>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <stack>#include <queue>#include <set>#include <map>using namespace std;#define M 324#define head 0#define SZ(v) ((int)(v).size())const int maxn = 350, maxe = 3300;char W[10][10];int t, inx, L[maxe], R[maxe], U[maxe], D[maxe], C[maxe], H[maxe], S[maxn], O[maxn];void remove(const int c){ L[R[c]] = L[c]; R[L[c]] = R[c]; for (int i = D[c]; i != c; i = D[i]) for (int j = R[i]; j != i; j = R[j]) { U[D[j]] = U[j]; D[U[j]] = D[j]; -- S[C[j]]; }}void resume(const int c){ for (int i = U[c]; i != c; i = U[i]) for (int j = L[i]; j != i; j = L[j]) { ++ S[C[j]]; D[U[j]] = j; U[D[j]] = j; } R[L[c]] = c; L[R[c]] = c;}bool dfs(const int k){ if (R[head] == head) return 1; int c, w = maxe; for (int i = R[head]; i != head; i = R[i]) if (S[i] < w) { c = i; w = S[i]; } remove(c); for (int i = D[c]; i != c; i = D[i]) { O[k] = H[i]; for (int j = R[i]; j != i; j = R[j]) remove(C[j]); if (dfs(k + 1)) return 1; for (int j = L[i]; j != i; j = L[j]) resume(C[j]); } resume(c); return 0;}void insert(int e, int r, int c){ ++ S[c]; C[inx] = c; H[inx] = r; D[U[c]] = inx; D[inx] = c; U[inx] = U[c]; U[c] = inx; if (e == -1) L[inx] = R[inx] = inx; else { R[L[e]] = inx; R[inx] = e; L[inx] = L[e]; L[e] = inx; } ++ inx;}int main(){ scanf("%d", &t); while (t --) { for (int i = 0; i < 9; ++ i) scanf("%s", W[i]); memset(S, 0, sizeof(S)); for (int i = 1; i <= M; ++ i) L[i + 1] = R[i - 1] = U[i] = D[i] = C[i] = i; L[head] = M; L[1] = head; R[M] = head; inx = M + 1; for (int i = 0; i < 9; ++ i) for (int j = 0; j < 9; ++ j) { if (W[i][j] == '0') for (int k = 1; k <= 9; ++ k) { int e = inx, r = (i * 9 + j) * 9 + k; insert(-1, r, i * 9 + k); insert(e, r, 81 + j * 9 + k); insert(e, r, 162 + (i / 3 * 3 + j / 3) * 9 + k); insert(e, r, 243 + i * 9 + j + 1); } else { int k = W[i][j] - '0'; int e = inx, r = (i * 9 + j) * 9 + k; insert(-1, r, i * 9 + k); insert(e, r, 81 + j * 9 + k); insert(e, r, 162 + (i / 3 * 3 + j / 3) * 9 + k); insert(e, r, 243 + i * 9 + j + 1); } } dfs(0); for (int i = 0; i < 81; ++ i) { int a = ((O[i] - 1) / 9) / 9; int b = ((O[i] - 1) / 9) % 9; int c = (O[i] - 1) % 9 + 1; W[a][b] = '0' + c; } for (int i = 0; i < 9; ++ i) { for (int j = 0; j < 9; ++ j) printf("%c", W[i][j]); printf("n"); } } return 0;}
