B. У строки есть цель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$. Можно ровно один раз применить к строке такую операцию: выбрать индекс $$$i$$$ и переставить символ $$$s_i$$$ в начало строки (удалив его на старой позиции). Например, если к строке «abaacd» применить операцию с индексом $$$i=4$$$ в нумерации с $$$1$$$, то получится строка «aabacd». Какую лексикографически минимальную$$$^{\dagger}$$$ строку можно получить одной такой операцией?

$$$^{\dagger}$$$Строка $$$a$$$ лексикографически меньше строки $$$b$$$ такой же длины, если и только если выполняется следующее:

  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

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

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

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

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

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

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

Пример
Входные данные
4
3
cba
4
acac
5
abbcb
4
aaba
Выходные данные
acb
aacc
abbcb
aaab
Примечание

В первом наборе нужно переместить последний символ в начало.

Во втором наборе входных данных нужно перенести в начало вторую букву «a».

В третьем наборе нужно применить операцию с $$$i=1$$$, тогда строка не изменится.