Anti-Sudoku

Cho một lời giải đúng của một câu đố Sudoku — một bảng $9\times 9$ gồm các chữ số từ $1$ đến $9$, trong đó mỗi hàng, mỗi cột và mỗi khối $3\times 3$ (các khối được chia theo cách thông thường của Sudoku) đều chứa đủ cả $9$ chữ số khác nhau.

Nhiệm vụ của bạn là thay đổi nhiều nhất $9$ ô của bảng (chọn một ô $(i,j)$ và đổi chữ số tại ô đó thành một chữ số bất kỳ trong khoảng $[1;9]$) sao cho bảng thu được trở thành một anti-sudoku, tức là bảng $9\times 9$ thỏa mãn đồng thời:

• Mọi chữ số trong bảng đều thuộc khoảng $[1;9]$;
• Mỗi hàng chứa ít nhất hai phần tử bằng nhau;
• Mỗi cột chứa ít nhất hai phần tử bằng nhau;
• Mỗi khối $3\times 3$ chứa ít nhất hai phần tử bằng nhau.

Dữ liệu đảm bảo luôn tồn tại đáp án. Nếu có nhiều đáp án, bạn có thể in ra bất kỳ đáp án nào hợp lệ.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $t$ — số lượng bộ dữ liệu.
• Mỗi bộ dữ liệu gồm $9$ dòng, mỗi dòng gồm $9$ ký tự từ $1$ đến $9$ không có khoảng trắng — lời giải đúng của một câu đố Sudoku.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra bảng kết quả gồm $9$ dòng sau khi đã thay đổi nhiều nhất $9$ ô để bảng trở thành anti-sudoku.

Ràng buộc

• $1\le t\le {10}^4$
• Mỗi bảng dữ liệu vào là một lời giải Sudoku hợp lệ.

Ví dụ