CF1735C.Phase Shift

There was a string $s$ which was supposed to be encrypted. For this reason, all $26$ lowercase English letters were arranged in a circle in some order, afterwards, each letter in $s$ was replaced with the one that follows in clockwise order, in that way the string $t$ was obtained.

You are given a string $t$. Determine the lexicographically smallest string $s$ that could be a prototype of the given string $t$.

A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if:

• in the first position where $a$ and $b$ differ, the string $a$ has a letter, that appears earlier in the alphabet than the corresponding letter in $b$.

曾有一个字符串 $s$ 需要被加密。为此，全部 $26$ 个小写英文字母以某种顺序围成一个环；随后，$s$ 中的每个字母都被其在该环中顺时针方向的下一个字母所替换，从而得到字符串 $t$。

现给出字符串 $t$。请确定可能生成该 $t$ 的字典序最小的原始字符串 $s$。

当且仅当满足以下条件时，等长字符串 $a$ 的字典序小于字符串 $b$：

• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中的字母在字母表中的顺序早于 $b$ 中对应位置的字母。

The first line of the input contains a single integer $t$ ($1 \le t \le 3 \cdot 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of the string $t$.

The next line contains the string $t$ of the length $n$, containing lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 3 \cdot 10^4$），表示测试用例的数量。随后是各测试用例的描述。

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

接下来的一行包含一个长度为 $n$ 的字符串 $t$，由小写英文字母组成。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a single line containing the lexicographically smallest string $s$ which could be a prototype of $t$.

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

In the first test case, we couldn't have the string "a", since the letter a would transit to itself. Lexicographically the second string "b" is suitable as an answer.

In the second test case, the string "aa" is not suitable, since a would transit to itself. "ab" is not suitable, since the circle would be closed with $2$ letters, but it must contain all $26$. The next string "ac" is suitable.

Below you can see the schemes for the first three test cases. The non-involved letters are skipped, they can be arbitrary placed in the gaps.

在第一个测试用例中，我们不能选择字符串 "a"，因为字母 a 会转移到其自身。按字典序，第二个字符串 "b" 是一个合适的答案。

在第二个测试用例中，字符串 "aa" 不合适，因为 a 会转移到其自身；"ab" 也不合适，因为该循环仅包含 2 个字母，但必须包含全部 26 个字母；下一个字符串 "ac" 是合适的。

下方展示了前三个测试用例的示意图。未涉及的字母被省略，它们可任意放置于空隙中。