有一个字符串 $$$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$$$ 的长度。
下一行包含长度为$$$n$$$的字符串$$$t$$$,包含小写英文字母。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行,其中包含按字典顺序最小的字符串 $$$s$$$,该字符串可能是 $$$t$$$ 的原型。
示例
输入 #1
5 1 a 2 ba 10 codeforces 26 abcdefghijklmnopqrstuvwxyz 26 abcdefghijklmnopqrstuvwxzy
输出 #1
b ac abcdebfadg bcdefghijklmnopqrstuvwxyza bcdefghijklmnopqrstuvwxyaz
注意
在第一个测试用例中,我们不能使用字符串“a”,因为字母 a 会转换为自身。按字典顺序,第二个字符串“b”适合作为答案。
在第二个测试用例中,字符串“aa”不合适,因为 a 会转换为自身。 “ab”不合适,因为圆圈将用 $$$2$$$ 字母封闭,但它必须包含所有 $$$26$$$。下一个字符串“ac”是合适的。
下面您可以看到前三个测试用例的方案。不涉及的字母将被跳过,它们可以任意放置在间隙中。