← 返回题目列表

Codeforces · 1805/B

B. 字符串有目标

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$。您可以将此操作应用于字符串一次:选择索引 $$$i$$$ 并将字符 $$$s_i$$$ 移动到字符串的开头(将其从旧位置删除)。例如,如果将索引 $$$i=4$$$ 的运算应用于从 $$$1$$$ 开始编号的字符串“abaacd”,则会得到字符串“aabacd”。通过此操作可以获得的按字典顺序最小的$$$^{\dagger}$$$ 字符串是多少?

$$$^{\dagger}$$$当且仅当以下条件成立时,字符串 $$$a$$$ 按字典顺序小于相同长度的字符串 $$$b$$$:

- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10 ^ 5$$$) — 字符串的长度。

每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,由小写英文字母组成。

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

输出

对于每个测试用例,在单独的行上打印对原始字符串应用一次操作后可以获得的按字典顺序排列的最小字符串。

示例

输入 #1

4
3
cba
4
acac
5
abbcb
4
aaba

输出 #1

acb
aacc
abbcb
aaab

注意

在第一个测试用例中,您需要将最后一个字符移到开头。

在第二种情况下,您需要移动第二个字母“a”。

在第三组中,您需要应用 $$$i=1$$$ 操作,则字符串不会改变。