Тодоку
Том — мастер в различных математико-теоретических дисциплинах. Недавно он основал исследовательскую лабораторию в нашем университете и обучает новичков, таких как Джим. На первом занятии он рассказал Джиму об игре Тудоку. Тудоку — это упрощенный вариант Судоку, поскольку на доске уже почти все числа расставлены. Такая доска остается, когда Том перестает решать обычное Судоку, ленясь заполнять последние несколько простых клеток. Теперь вам нужно помочь Джиму решить все Тудоку, которые Том оставил для него.
Судоку играется на 9×9 доске, разделенной на девять 3×3 блоков. Изначально на доске есть только несколько чисел, и цель состоит в том, чтобы заполнить оставшиеся клетки так, чтобы в каждом рядке, столбце и 3×3 блоке были все числа от 1 до 9. Это может быть довольно сложно, но помните, что Том уже заполнил большинство клеток. Решить доску Тудоку можно, многократно применяя следующее правило: если в каком-либо рядке, столбце или 3×3 блоке ровно восемь чисел, заполните оставшееся.
В следующем примере все еще отсутствуют три клетки. Верхнюю левую клетку нельзя определить напрямую, так как ни в её рядке, ни в столбце, ни в блоке нет восьми чисел. Однако, недостающее число для правой клетки можно определить, используя вышеупомянутое правило, так как её столбец содержит ровно восемь чисел. Аналогично, число для самой нижней свободной клетки можно определить, исследуя её рядок. Наконец, последнюю свободную клетку можно заполнить, посмотрев на её рядок, столбец или блок.
Входные данные
Первая строка содержит количество сценариев. Для каждого сценария ввод состоит из девяти строк, каждая из которых содержит девять цифр. Нули обозначают клетки, которые не были заполнены Томом и должны быть заполнены вами. Каждый сценарий завершается пустой строкой.
Выходные данные
Вывод для каждого сценария начинается со строки "Сценарий #i:", где i — номер сценария, начиная с 1. Затем выведите решенную доску Тудоку в том же формате, что и ввод, но с заменой нулей на правильные цифры. Завершите вывод для каждого сценария пустой строкой.