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