Вам дано корректное решение головоломки судоку. Если вы не знаете, что такое судоку, то вы можете прочитать об этом здесь.
Картинка, показывающая корректное решение судоку:
Блоки ограничены жирным черным цветом.
Ваша задача — заменить не более \(9\) элементов этого поля (то есть, выбрать некоторые \(1 \le i, j \le 9\) и заменить число в позиции \((i, j)\) на любое другое число в отрезке \([1; 9]\)), чтобы получить анти-судоку. Анти-судоку — это поле размера \(9 \times 9\), в котором:
- Каждое число на этом поле находится в отрезке \([1; 9]\);
- каждая строка содержит как минимум два одинаковых элемента;
- каждый столбец содержит как минимум два одинаковых элемента;
- каждый блок размера \(3 \times 3\) (о том, что такое блок, вы можете прочитать по ссылке выше) содержит как минимум два одинаковых элемента.
Гарантируется, что ответ существует.
Вам нужно ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него — заданное изначально поле с не более, чем \(9\) измененными в нем элементами так, что полученное поле является анти-судоку. Если существует несколько подходящих решений, вы можете вывести любое. Гарантируется, что ответ существует.