Судоку

Судоку - это очень простая задача. Квадратная таблица из 9 строк и 9 столбцов разделена на 9 меньших квадратов 3×3, как показано на рисунке. В некоторых клетках записаны десятичные цифры от 1 до 9. Другие клетки пусты. Цель состоит в том, чтобы заполнить пустые клетки десятичными цифрами от 1 до 9, по одной цифре в клетке, таким образом, чтобы в каждой строке, в каждом столбце и в каждой отмеченном подквадрате 3×3, были все цифры от 1 до 9. Напишите программу для решения данной задачи судоку.

Входные данные

Входные данные начинаются со строки с количеством тестов. Для каждого теста далее следует 9 строк, содержащие соответствующе строки таблицы. В каждой строке размещено ровно 9 десятичных цифр, соответствующие цифрам в ячейках этой строки. Если ячейка пуста, во входных данных в ней содержится цифра ​​0.

Выходные данные

Для каждого теста ваша программа должна вывести решение в том же формате, что и во входных данных. Пустые ячейки должны быть заполнены в соответствии с правилами. Если решение не является уникальным, то программа может вывести любое из них.

Выходные данные для различных тестовых случаев разделяйте пустой строкой.

Примеры