Задачи
Су-су-судоку
Су-су-судоку
В настоящее время практически все играли в судоку: вам задано таблицу из ячеек \textbf{9} на \textbf{9}, которую вы должны заполнить цифрами от \textbf{1} по \textbf{9} так, что
\begin{enumerate}
\item каждая строка имеет все девять цифр,
\item каждый столбец имеет все девять цифр, и
\item все девять подквадратов \textbf{3} на \textbf{3} имеют все девять цифр.
\end{enumerate}
Перед началом игры вы получаете частично заполненную таблицу, и вас просят заполнить оставшуюся часть квадрата. Одна из таких головоломок приведена ниже.
\includegraphics{https://static.e-olymp.com/content/33/33c7eb62c9077e8685a3973fbcd4aabe04b078fd.jpg}
В этой задаче вам будет предоставлена почти завершенная таблица Судоку, вы заполнили до этого почти все клетки, за исключением пяти. Вас попросили закончить заполнение таблицы, или определить, что это невозможно (Вы, возможно, уже сделали ошибку!).
\InputFile
Первая строка входных данных будет содержать натуральное число, указывающее на количество последующих тестов. Каждый тест будет представлять практически завершенную таблицу Судоку, состоять из \textbf{9} строк, каждая из которых содержит \textbf{9} символов из набора цифр от \textbf{0} до \textbf{9}. Там будет ровно пять \textbf{0} в каждом тесте, указывающих на пять незаполненных клеток.
\OutputFile
Для каждого теста должен быть выведено
\textbf{Could not complete this grid.}
если невозможно выполнить заполнение таблицы в соответствии с правилами игры, или вывести заполненную таблицу в формате, показанном ниже (в выходных данных нет пробелов). Если есть способ завершить заполнение сетки, то он будет уникальным. Отделяйте разные тесты пустой строкой.
Входные данные #1
2 481253697 267948105 539671204 654389712 908704563 173562849 702136958 315897426 896425371 481253697 267948105 539671284 654289710 908704562 173562849 702136958 315897426 896425371
Выходные данные #1
481253697 267948135 539671284 654389712 928714563 173562849 742136958 315897426 896425371 Could not complete this grid.