C. Черепаха и хорошие пары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Черепаха считает пару целых чисел $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) приятной парой, если и только если существует целое число $$$k$$$, такое что $$$i \le k < j$$$ и выполняются оба из следующих двух условий:

  • $$$s_k \ne s_{k + 1}$$$;
  • $$$s_k \ne s_i$$$ или $$$s_{k + 1} \ne s_j$$$.

Кроме того, Черепаха считает пару целых чисел $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) хорошей парой, если и только если $$$s_i = s_j$$$ или $$$(i, j)$$$ является приятной парой.

Черепаха хочет переставить буквы в строке $$$s$$$ так, чтобы количество хороших пар было максимизировано. Пожалуйста, помогите ей!

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

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

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

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

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

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

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

Пример
Входные данные
5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces
Выходные данные
acb
ddedf
urtlet
pppppppp
codeforces
Примечание

В первом наборе $$$(1, 3)$$$ является хорошей парой в строке из переставленных букв. Можно заметить, что мы не можем переставить буквы так, чтобы количество хороших пар было больше $$$1$$$. bac и cab также могут быть ответом.

Во втором наборе $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(3, 5)$$$ являются хорошими парами в строке из переставленных букв. efddd также может быть ответом.