Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

H. 378QAQ и ядро
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У 378QAQ есть строка $$$s$$$ длины $$$n$$$. Определим ядро строки как подстроку$$$^\dagger$$$ с максимальным лексикографическим$$$^\ddagger$$$ порядком.

Например, ядром «$$$\mathtt{bazoka}$$$» является «$$$\mathtt{zoka}$$$», а ядром «$$$\mathtt{aaa}$$$» является «$$$\mathtt{aaa}$$$».

378QAQ хочет переставить символы в строке $$$s$$$ так, чтобы ядро было лексикографически минимальным. Найдите лексикографически минимальное возможное ядро среди всех перестановок $$$s$$$.

$$$^\dagger$$$ Подстрока строки $$$s$$$ — это непрерывный отрезок букв из $$$s$$$. Например, «$$$\mathtt{defor}$$$», «$$$\mathtt{code}$$$» и «$$$\mathtt{o}$$$» являются подстроками «$$$\mathtt{codeforces}$$$», а «$$$\mathtt{codes}$$$» и «$$$\mathtt{aaa}$$$» не являются.

$$$^\ddagger$$$ Строка $$$p$$$ лексикографически меньше строки $$$q$$$ тогда и только тогда, когда выполняется одно из следующих условий:

  • $$$p$$$ является префиксом $$$q$$$, но $$$p \ne q$$$; или
  • в первой позиции, где $$$p$$$ и $$$q$$$ отличаются, строка $$$p$$$ имеет меньший символ, чем символ на соответствующей поозиции в $$$q$$$ (при сравнении по их ASCII-коду).

Например, «$$$\mathtt{code}$$$» и «$$$\mathtt{coda}$$$» лексикографически меньше, чем «$$$\mathtt{codeforces}$$$», а «$$$\mathtt{codeforceston}$$$» и «$$$\mathtt{z}$$$» — нет.

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

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

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

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

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

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

Для каждого набора входных данных выведите лексикографически минимальное возможное ядро среди всех перестановок $$$s$$$.

Пример
Входные данные
6
3
qaq
4
cccc
6
bazoka
6
zazzzz
7
ababbbb
7
ccbabcc
Выходные данные
qaq
cccc
z
zzz
bbababb
cbcacbc
Примечание

В первом наборе входных данных все возможные перестановки и соответствующие им ядра выглядят следующим образом:

  • «$$$\mathtt{qaq}$$$», его ядро — «$$$\mathtt{qaq}$$$».
  • «$$$\mathtt{aqq}$$$», его ядро — «$$$\mathtt{qq}$$$».
  • «$$$\mathtt{qqa}$$$», его ядро — «$$$\mathtt{qqa}$$$».

Таким образом, ядро с минимальным лексикографическим порядком среди всех перестановок — это «$$$\mathtt{qaq}$$$».