C. Сдвиг по фазе
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Вам дали строку $$$t$$$. Определите лексикографически минимальную строку $$$s$$$, из которой могла быть получена данная строка $$$t$$$.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$ такой же длины, если и только если:

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

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

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

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

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

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

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

Пример
Входные данные
5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy
Выходные данные
b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz
Примечание

В первом наборе входных данных мы не могли иметь строку «a», поскольку тогда буква a переходила бы сама в себя, что невозможно. В качестве ответа нам подходит лексикографически вторая строка «b».

Во втором наборе нам не подходит «aa», поскольку a переходила бы в себя, и не подходит «ab», поскольку круг переходов замкнулся бы на $$$2$$$ буквах, а он должен состоять из всех $$$26$$$. Следующая строка «ac» нам подходит.

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