模拟+DFS。
/* 2780 */
#include <cstdio>
#include <cstring>
#include <cstdlib> char map[][];
int visit[][][];
int fn;
int fx[], fy[]; bool dfs(int n) {
if (n == )
return true;
int i = fx[n], j = fy[n], k, r; for (k=; k<=; ++k) {
if (!visit[i][j][k]) {
map[i][j] = k;
visit[i][j][k]++;
for (r=; r<; ++r) {
visit[i][r][k]++;
visit[r][j][k]++;
visit[i/*+k/][j/*+k%][k]++;
}
if (dfs(n-))
return true;
visit[i][j][k]--;
for (r=; r<; ++r) {
visit[i][r][k]--;
visit[r][j][k]--;
visit[i/*+k/][j/*+k%][k]--;
}
}
}
return false;
} bool check() {
int i, j, k;
int x, y, in;
bool f[]; // check row
for (i=; i<; ++i) {
memset(f, false, sizeof(f));
for (j=; j<; ++j) {
if (map[i][j] && f[map[i][j]]) {
return true;
}
f[map[i][j]] = true;
}
} // check line
for (j=; j<; ++j) {
memset(f, false, sizeof(f));
for (j=; j<; ++j) {
if (map[i][j] && f[map[i][j]]) {
return true;
}
f[map[i][j]] = true;
}
} // check sub
for (x=; x<; ++x) {
memset(f, false, sizeof(f));
for (y=; y<; ++y) {
i = x/* + y/;
j = x%* + y%;
if (map[i][j] && f[map[i][j]]) {
return true;
}
f[map[i][j]] = true;
}
} return false;
} int main() {
int t;
int i, j, k;
bool flag; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d", &t);
while (t--) {
memset(visit, , sizeof(visit));
fn = ;
for (i=; i<; ++i) {
scanf("%s", map[i]);
for (j=; j<; ++j) {
map[i][j] -= '';
if (map[i][j] == ) {
fx[fn] = i;
fy[fn] = j;
++fn;
} else {
for (k=; k<; ++k) {
visit[i][k][map[i][j]]++;
visit[k][j][map[i][j]]++;
visit[i/*+k/][j/*+k%][map[i][j]]++;
}
}
}
}
if (check()) {
flag = false;
} else {
flag = dfs();
}
if (flag) {
for (i=; i<; ++i) {
for (j=; j<; ++j)
map[i][j] += '';
puts(map[i]);
}
} else {
puts("Could not complete this grid.");
}
if (t)
printf("\n");
} return ;
}