题目描述

有一个字符串 $s$ 需要被加密。为此，所有 $26$ 个小写英文字母被以某种顺序排列成一个环，然后将 $s$ 中的每个字母替换为顺时针方向的下一个字母，从而得到字符串 $t$。

现在给定字符串 $t$，请你确定可能作为原型字符串 $s$ 的字典序最小的字符串。

对于长度相同的字符串 $a$ 和 $b$，如果在第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前，则称 $a$ 的字典序小于 $b$。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 3 \times 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。

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

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

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

输出格式

对于每个测试用例，输出一行，表示可能作为 $t$ 原型的字典序最小的字符串 $s$。

说明/提示

在第一个测试用例中，字符串 "a" 不可能作为答案，因为字母 a 会映射到自身。字典序第二小的字符串 "b" 是合适的答案。

在第二个测试用例中，字符串 "aa" 不合适，因为 a 会映射到自身。"ab" 也不合适，因为环中只包含了 $2$ 个字母，但必须包含所有 $26$ 个字母。下一个字符串 "ac" 是合适的答案。

下图展示了前三个测试用例的方案。未涉及的字母可以任意填入空隙中。

由 ChatGPT 4.1 翻译

样例

5
1
a
2
ba
10
codeforces
26
abcdefghijklmnopqrstuvwxyz
26
abcdefghijklmnopqrstuvwxzy

b
ac
abcdebfadg
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz