#include <bits/stdc++.h>
class Sudoku {
std::vector<std::string> board{9};
bool is_valid(int row, int col, char digit) {
for (int i = 0; i < 9; ++i)
if (board[row][i] == digit ||
board[i][col] == digit ||
board[row / 3 * 3 + i / 3][col / 3 * 3 + i % 3] == digit)
return false;
return true;
}
public:
void read() {
for(auto &row : board)
std::getline(std::cin, row);
}
void print() const {
for(auto &row : board)
std::cout << row << '\n';
}
bool solve(int row = 0, int col = 0) {
if (col == 9) return solve(row + 1, 0);
if (row == 9) return true;
if (board[row][col] != '0')
return solve(row, col + 1);
for (char d = '1'; d <= '9'; ++d)
if (is_valid(row, col, d)) {
board[row][col] = d;
if (solve(row, col + 1))
return true;
board[row][col] = '0';
}
return false;
}
};
int main() {
Sudoku sudoku{};
int n;
std::cin >> n;
std::cin.ignore();
while (n--) {
sudoku.read();
sudoku.solve();
sudoku.print();
std::cout << '\n';
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgpjbGFzcyBTdWRva3UgewogICAgc3RkOjp2ZWN0b3I8c3RkOjpzdHJpbmc+IGJvYXJkezl9OwoKICAgIGJvb2wgaXNfdmFsaWQoaW50IHJvdywgaW50IGNvbCwgY2hhciBkaWdpdCkgewogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgOTsgKytpKQogICAgICAgICAgICBpZiAoYm9hcmRbcm93XVtpXSA9PSBkaWdpdCB8fAogICAgICAgICAgICAgICAgYm9hcmRbaV1bY29sXSA9PSBkaWdpdCB8fAogICAgICAgICAgICAgICAgYm9hcmRbcm93IC8gMyAqIDMgKyBpIC8gM11bY29sIC8gMyAqIDMgKyBpICUgM10gPT0gZGlnaXQpCiAgICAgICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICB9CgpwdWJsaWM6CiAgICB2b2lkIHJlYWQoKSB7CiAgICAgICAgZm9yKGF1dG8gJnJvdyA6IGJvYXJkKQogICAgICAgICAgICBzdGQ6OmdldGxpbmUoc3RkOjpjaW4sIHJvdyk7CiAgICB9CgogICAgdm9pZCBwcmludCgpIGNvbnN0IHsKICAgICAgICBmb3IoYXV0byAmcm93IDogYm9hcmQpCiAgICAgICAgICAgIHN0ZDo6Y291dCA8PCByb3cgPDwgJ1xuJzsKICAgIH0KCiAgICBib29sIHNvbHZlKGludCByb3cgPSAwLCBpbnQgY29sID0gMCkgewogICAgICAgIGlmIChjb2wgPT0gOSkgcmV0dXJuIHNvbHZlKHJvdyArIDEsIDApOwogICAgICAgIGlmIChyb3cgPT0gOSkgcmV0dXJuIHRydWU7CiAgICAgICAgaWYgKGJvYXJkW3Jvd11bY29sXSAhPSAnMCcpCiAgICAgICAgICAgIHJldHVybiBzb2x2ZShyb3csIGNvbCArIDEpOwogICAgICAgIGZvciAoY2hhciBkID0gJzEnOyBkIDw9ICc5JzsgKytkKQogICAgICAgICAgICBpZiAoaXNfdmFsaWQocm93LCBjb2wsIGQpKSB7CiAgICAgICAgICAgICAgICBib2FyZFtyb3ddW2NvbF0gPSBkOwogICAgICAgICAgICAgICAgaWYgKHNvbHZlKHJvdywgY29sICsgMSkpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgICAgICAgICBib2FyZFtyb3ddW2NvbF0gPSAnMCc7CiAgICAgICAgICAgIH0KICAgICAgICByZXR1cm4gZmFsc2U7CiAgICB9Cn07CgppbnQgbWFpbigpIHsKICAgIFN1ZG9rdSBzdWRva3V7fTsKICAgIGludCBuOwogICAgc3RkOjpjaW4gPj4gbjsKICAgIHN0ZDo6Y2luLmlnbm9yZSgpOwogICAgd2hpbGUgKG4tLSkgewogICAgICAgIHN1ZG9rdS5yZWFkKCk7CiAgICAgICAgc3Vkb2t1LnNvbHZlKCk7CiAgICAgICAgc3Vkb2t1LnByaW50KCk7CiAgICAgICAgc3RkOjpjb3V0IDw8ICdcbic7CiAgICB9Cn0=