eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Судоку

Судоку

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Судоку - это очень простая задача. Квадратная таблица из 9 строк и 9 столбцов разделена на 9 меньших квадратов 3×3, как показано на рисунке. В некоторых клетках записаны десятичные цифры от 1 до 9. Другие клетки пусты. Цель состоит в том, чтобы заполнить пустые клетки десятичными цифрами от 1 до 9, по одной цифре в клетке, таким образом, чтобы в каждой строке, в каждом столбце и в каждой отмеченном подквадрате 3×3, были все цифры от 1 до 9. Напишите программу для решения данной задачи судоку.

Входные данные

Входные данные начинаются со строки с количеством тестов. Для каждого теста далее следует 9 строк, содержащие соответствующе строки таблицы. В каждой строке размещено ровно 9 десятичных цифр, соответствующие цифрам в ячейках этой строки. Если ячейка пуста, во входных данных в ней содержится цифра ​​0.

Выходные данные

Для каждого теста ваша программа должна вывести решение в том же формате, что и во входных данных. Пустые ячейки должны быть заполнены в соответствии с правилами. Если решение не является уникальным, то программа может вывести любое из них.

Выходные данные для различных тестовых случаев разделяйте пустой строкой.

Пример

Входные данные #1
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Выходные данные #1
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127