题目描述

Y同学有一个字符串 $s$ 需要被加密。Y同学的加密方法是将所有 26 个小写英文字母都按某种顺序排列成一个圆圈，然后， $s$ 中的每个字母都被替换为顺时针顺序后面的字母，这样就得到了字符串 t。

现在Y得到了一个字符串 t。尝试构造一种加密方法来得到t的原文s，答案可能会有多个，需要你输出按照字典序最小的那个。

字符串 a 在字典顺序上小于相同长度的字符串 b，当且仅当：

在 A 和 B 不同的第一个位置，字符串 A 有一个字母，该字母在字母表中出现的时间早于 B 中的相应字母。

输入格式

输入包含多组测试用例

输入的第一行包含一个整数 $t （1≤t≤3*{10^4}）$ — 测试用例的数量。测试用例的说明如下。

每个测试用例的第一行包含一个整数 $n （1≤n≤10^5）$ — 字符串 t 的长度。

下一行包含长度为 n 的字符串 t，包含小写英文字母。

保证所有测试用例中 n 的总和不超过 $2*10^5$ 。

对于每个测试用例，输出一行包含字典顺序最小的字符串 s，该字符串可以是 t 的原型。

5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy

b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz

样例解释：对于样例1：a不能被替换为a，如果这样做，那么就会使a指向a，成为一个自环，而希望的加密方法是将26个字母连成一个环。所以a的原文为b是一个好的方案。

对于样例2：aa是不行的，理由和样例一一样，a和a自己成环。ab也是不行的，a指向b，b指向a，那么还是只有ab的环。ac是一个好的方案。