310251: CF1805B. The String Has a Target

B. The String Has a Targettime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a string $s$. You can apply this operation to the string exactly once: choose index $i$ and move character $s_i$ to the beginning of the string (removing it at the old position). For example, if you apply the operation with index $i=4$ to the string "abaacd" with numbering from $1$, you get the string "aabacd". What is the lexicographically minimal$^{\dagger}$ string you can obtain by this operation?

$^{\dagger}$A string $a$ is lexicographically smaller than a string $b$ of the same length if and only if the following holds:

• 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$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

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

The second line of each test case contains the string $s$ of length $n$, consisting of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10 ^ 5$.

Output

For each test case, on a separate line print the lexicographically smallest string that can be obtained after applying the operation to the original string exactly once.

ExampleInput

4
3
cba
4
acac
5
abbcb
4
aaba

Output

acb
aacc
abbcb
aaab

Note

In the first test case, you need to move the last character to the beginning.

In the second case, you need to move the second letter "a".

In the third set you need to apply the operation with $i=1$, then the string will not change.

题目大意：
给定一个字符串 s。你可以对字符串执行一次操作：选择一个索引 i 并将字符 s_i 移动到字符串的开头（在原来的位置上删除它）。例如，如果你对编号从 1 开始的字符串 "abaacd" 应用索引 i=4 的操作，你会得到字符串 "aabacd"。通过这次操作，你能得到的最小字典序字符串是什么？

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含一个整数 n（1 ≤ n ≤ 10^5）——字符串的长度。
- 第二行包含一个长度为 n 的由小写英文字母组成的字符串 s。
- 保证所有测试用例的 n 之和不超过 10^5。

输出：
- 对于每个测试用例，输出一行，表示通过一次操作后能得到的最小字典序字符串。

示例：
输入：
```
4
3
cba
4
acac
5
abbcb
4
aaba
```
输出：
```
acb
aacc
abbcb
aaab
```

注意：
- 在第一个测试用例中，你需要将最后一个字符移动到开头。
- 在第二个测试用例中，你需要移动第二个字母 "a"。
- 在第三个测试用例中，你需要应用 i=1 的操作，然后字符串将不会改变。题目大意： 给定一个字符串 s。你可以对字符串执行一次操作：选择一个索引 i 并将字符 s_i 移动到字符串的开头（在原来的位置上删除它）。例如，如果你对编号从 1 开始的字符串 "abaacd" 应用索引 i=4 的操作，你会得到字符串 "aabacd"。通过这次操作，你能得到的最小字典序字符串是什么？ 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含一个整数 n（1 ≤ n ≤ 10^5）——字符串的长度。 - 第二行包含一个长度为 n 的由小写英文字母组成的字符串 s。 - 保证所有测试用例的 n 之和不超过 10^5。 输出： - 对于每个测试用例，输出一行，表示通过一次操作后能得到的最小字典序字符串。 示例： 输入： ``` 4 3 cba 4 acac 5 abbcb 4 aaba ``` 输出： ``` acb aacc abbcb aaab ``` 注意： - 在第一个测试用例中，你需要将最后一个字符移动到开头。 - 在第二个测试用例中，你需要移动第二个字母 "a"。 - 在第三个测试用例中，你需要应用 i=1 的操作，然后字符串将不会改变。