Су-су-судоку
В даний час практично усі грали в судоку: вам задано таблицю з комірок 9 на 9, яку ви повинні заповнити цифрами від 1 до 9 так, що
кожен рядок містить усі дев'ять цифр,
кожен стовбець містить усі дев'ять цифр, і
усі дев'ять підквадратів 3 на 3 містять усі дев'ять цифр.
Перед початком гри ви отримуєте частково заповнену таблицю, і вас просять заповнити ту частину квадрата, що залишилась. Одну з таких ломиголовок наведено нижче.
У цій задачі вам буде надано майже завершену таблицю Судоку, ви заповнили до цього майже усі клітинки, за винятном п'яти. Вас попросили завершити заповнення таблиці, або визначити, що це неможливо (Ви, можливо, вже зробили помилку!).
Вхідні дані
Перший рядок вхідних даних буде містити натуральне число, яке вказує на кількість наступних тестів. Кожен тест буде являти практично завершену таблицю Судоку, складатись з 9 рядків, кожен з яких містить 9 символів з набору цифр від 0 до 9. Там буде рівно п'ять 0 у кожному тесті, які вказують на п'ять незаповнених клітинок.
Вихідні дані
Для кожного тесту потрібно вивести
Could not complete this grid.
якщо неможливо виконати заповнення таблиці у відповідності з правилами гри, або вивести заповнену таблицю у форматі, наведеному нижче (у вихідних даних відсутні пропуски). Якщо є спосіб завершити заповнення сітки, то він буде унікальним. Відокремлюйте різні тести порожнім рядком.