[Solution] Phase Shift Codeforces Solution

C. Phase Shift

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

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

Input

The first line of the input contains a single integer t$t$ (1≤t≤3⋅104$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$n$ (1≤n≤105$1\le n\le {10}^5$) — the length of the string t$t$.

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

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

Output

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

Note

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$2$ letters, but it must contain all 26$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.