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

Су-су-судоку

Су-су-судоку

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

В даний час практично усі грали в судоку: вам задано таблицю з комірок 9 на 9, яку ви повинні заповнити цифрами від 1 до 9 так, що

  1. кожен рядок містить усі дев'ять цифр,

  2. кожен стовбець містить усі дев'ять цифр, і

  3. усі дев'ять підквадратів 3 на 3 містять усі дев'ять цифр.

Перед початком гри ви отримуєте частково заповнену таблицю, і вас просять заповнити ту частину квадрата, що залишилась. Одну з таких ломиголовок наведено нижче.

У цій задачі вам буде надано майже завершену ​таблицю ​Судоку, ви заповнили до цього майже усі клітинки, за винятном п'яти. Вас попросили завершити заповнення таблиці, або визначити, що це неможливо (Ви, можливо, вже зробили помилку!).

Вхідні дані

Перший рядок вхідних даних буде містити натуральне число, яке вказує на кількість наступних тестів. Кожен тест буде являти практично завершену таблицю Судоку, складатись з 9 рядків, кожен з яких містить 9 символів з набору цифр від 0 до 9. Там буде рівно п'ять 0 у кожному тесті, які вказують на п'ять незаповнених клітинок.

Вихідні дані

Для кожного тесту потрібно вивести

Could not complete this grid.

якщо неможливо виконати заповнення таблиці у відповідності з правилами гри, або вивести заповнену таблицю у форматі, наведеному нижче (у вихідних даних відсутні пропуски). Якщо є спосіб завершити заповнення сітки, то він буде унікальним. Відокремлюйте різні тести порожнім рядком.

Приклад

Вхідні дані #1
2 
481253697
267948105
539671204
654389712
908704563
173562849
702136958
315897426
896425371
481253697
267948105
539671284
654289710
908704562
173562849
702136958
315897426
896425371
Вихідні дані #1
481253697
267948135
539671284
654389712
928714563
173562849
742136958
315897426
896425371

Could not complete this grid.