Судоку#3522
Судоку — це дуже проста задача. Квадратну таблицю з рядків та стовпців розділено на менших квадратів 3 \times 3, як показано на рисунку. У деяких клітинках записано десяткові цифри від до . Інші клітинки порожні. Мета полягає у тому, щоб заповнити порожні клітинки десятковими цифрами від до , по одній цифрі у клітинці, таким чином, щоб у кожному рядку, у кожному стовпці і у кожному відміченому підквадраті 3 \times 3 були усі цифри від до . Напишіть програму для розв'язання заданої задачі судоку.
Вхідні дані починаються з рядка з кількістю тестів. Для кожного тесту далі йде рядків, які містять відповідні рядки таблиці. У кожному рядку розміщено рівно десяткових цифр, які відповідають цифрам у клітинках цього рядка. Якщо клітинка порожня, у вхідних даних у ній міститься цифра .
Для кожного тесту ваша програма повинна вивести розв'язок у тому ж форматі, що і у вхідних даних. Порожні клітинки повинні бути заповнені у відповідності з правилами. Якщо розв'язок не є унікальним, то програма може вивести довільний з них.
Вихідні дані для різних тестових випадків розділяйте порожнім рядком.
Приклад 1