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

У вас есть строка $$$s_1 s_2 \ldots s_n$$$, вы стоите слева от нее и смотрите направо. Вы хотите выбрать индекс $$$k$$$ ($$$1 \le k \le n$$$) и поставить зеркало после $$$k$$$-го символа строки, таким образом, вы будете видеть строку $$$s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1$$$. Какую лексикографически минимальную строку вы можете увидеть?

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$): количество наборов входных данных.

Следующие $$$t$$$ строк содержат описания наборов, по две строки на набор.

В первой строке записано целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$): длина строки.

Во второй строке записана строка $$$s$$$ длины $$$n$$$, состоящая из маленьких латинских букв.

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

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

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

Пример
Входные данные
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa
Выходные данные
cc
cbaabc
aa
bb
Примечание

В первом примере выберем $$$k = 1$$$, чтобы получить «cc».

Во втором примере выберем $$$k = 3$$$, чтобы получить «cbaabc».

В третьем примере выберем $$$k = 1$$$, чтобы получить «aa».

В четвертом примере выберем $$$k = 1$$$, чтобы получить «bb».