Су-су-судоку
В настоящее время практически все играли в судоку: вам задано таблицу из ячеек 9 на 9, которую вы должны заполнить цифрами от 1 по 9 так, что
каждая строка имеет все девять цифр,
каждый столбец имеет все девять цифр, и
все девять подквадратов 3 на 3 имеют все девять цифр.
Перед началом игры вы получаете частично заполненную таблицу, и вас просят заполнить оставшуюся часть квадрата. Одна из таких головоломок приведена ниже.
В этой задаче вам будет предоставлена почти завершенная таблица Судоку, вы заполнили до этого почти все клетки, за исключением пяти. Вас попросили закончить заполнение таблицы, или определить, что это невозможно (Вы, возможно, уже сделали ошибку!).
Входные данные
Первая строка входных данных будет содержать натуральное число, указывающее на количество последующих тестов. Каждый тест будет представлять практически завершенную таблицу Судоку, состоять из 9 строк, каждая из которых содержит 9 символов из набора цифр от 0 до 9. Там будет ровно пять 0 в каждом тесте, указывающих на пять незаполненных клеток.
Выходные данные
Для каждого теста должен быть выведено
Could not complete this grid.
если невозможно выполнить заполнение таблицы в соответствии с правилами игры, или вывести заполненную таблицу в формате, показанном ниже (в выходных данных нет пробелов). Если есть способ завершить заполнение сетки, то он будет уникальным. Отделяйте разные тесты пустой строкой.