C. Равные частоты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовём строку сбалансированной, если все символы, которые в ней присутствуют, входят в неё одинаковое число раз. Например, «coder», «appall» и «ttttttt» — сбалансированные строки, а «wowwow» и «codeforces» — нет.

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв. Найдите сбалансированную строку $$$t$$$ той же длины $$$n$$$, состоящую из строчных латинских букв и отличающуюся от строки $$$s$$$ в как можно меньшем числе позиций. Другими словами, число индексов $$$i$$$ таких, что $$$s_i \ne t_i$$$, должно быть минимальным возможным.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длину строки $$$s$$$.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

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

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

Пример
Входные данные
4
5
hello
10
codeforces
5
eevee
6
appall
Выходные данные
1
helno
2
codefofced
1
eeeee
0
appall
Примечание

В первом наборе входных данных заданная строка «hello» не является сбалансированной: буквы «h», «e» и «o» встречаются в ней по одному разу, а буква «l» — два раза. С другой стороны, строка «helno» сбалансирована: в ней присутствуют пять разных букв, и каждая из них встречается ровно один раз. Строки «hello» и «helno» отличаются всего в одной позиции — в четвёртом символе. Возможны и другие решения.

Во втором наборе входных данных строка «codefofced» сбалансирована, так как в ней присутствуют только буквы «c», «o», «d», «e» и «f», и каждая из них встречается ровно два раза.

В третьем наборе входных данных строка «eeeee» сбалансирована, так как в ней присутствует только буква «e».

В четвёртом наборе входных данных заданная строка «appall» уже сбалансирована.