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