ПИН-код — это строка, которая состоит ровно из \(4\) цифр. Примеры возможных ПИН-кодов: «7013», «0000» и «0990». Обратите внимание, что ПИН-код может начинаться с любой цифры, даже с 0.
У Поликарпа есть \(n\) (\(2 \le n \le 10\)) банковских карт, ПИН-код \(i\)-й карты равен \(p_i\).
Недавно Поликарп прочёл рекомендацию, что на разные карты лучше устанавливать различные ПИН-коды. Поэтому он хочет поменять наименьшее количество цифр в ПИН-кодах своих карт так, чтобы все \(n\) кодов оказались различными.
Формально говоря, за один шаг Поликарп берёт одну банковскую карту с номером \(i\) (\(1 \le i \le n\)), затем в её ПИН-коде \(p_i\) выбирает одну позицию (от \(1\) до \(4\)), и изменяет цифру в этой позиции на любую другую. Ему необходимо за наименьшее количество шагов сделать так, чтобы не существовало пары одинаковых ПИН-кодов.
Поликарп быстро справился с этой задачей. А сможете ли вы её решить?
Выходные данные
Выведите ответы на \(t\) заданных наборов входных данных. Ответ на каждый набор должен состоять из \(n + 1\) строки.
В первую строку выведите \(k\) — наименьшее количество изменений, чтобы сделать все ПИН-коды различными. Далее в \(n\) строках выведите изменённые ПИН-коды в порядке, соответствующем их порядку во входных данных. Если существует несколько оптимальных ответов, выведите любой из них.