CF1735C Phase Shift

有一个字符串 $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 翻译