378QAQ 有一个长度为 $$$n$$$ 的字符串 $$$s$$$。将字符串的核心定义为具有最大字典序$$$^\ddagger$$$ 顺序的子字符串$$$^\dagger$$$。
例如,“$$$\mathtt{bazoka}$$$”的核心是“$$$\mathtt{zoka}$$$”,“$$$\mathtt{aaa}$$$”的核心是“$$$\mathtt{aaa}$$$”。
378QAQ 想要重新排列字符串 $$$s$$$,以便核心按字典顺序最小。在 $$$s$$$ 的所有重新排列中找到按字典顺序排列的最小可能核心。
$$$^\dagger$$$ 字符串 $$$s$$$ 的子字符串是来自 $$$s$$$ 的连续字母段。例如,“$$$\mathtt{defor}$$$”、“$$$\mathtt{code}$$$”和“$$$\mathtt{o}$$$”都是“$$$\mathtt{codeforces}$$$”的子字符串,而“$$$\mathtt{codes}$$$”和“$$$\mathtt{aaa}$$$”是不。
$$$^\ddagger$$$ 当且仅当满足以下条件之一时,字符串 $$$p$$$ 按字典顺序小于字符串 $$$q$$$:
- $$$p$$$ 是 $$$q$$$ 的前缀,但 $$$p \ne q$$$;或
- 在 $$$p$$$ 和 $$$q$$$ 不同的第一个位置,字符串 $$$p$$$ 的元素比 $$$q$$$ 中的相应元素小(通过它们的 ASCII 代码进行比较)。
例如,“$$$\mathtt{code}$$$”和“$$$\mathtt{coda}$$$”在字典顺序上都小于“$$$\mathtt{codeforces}$$$”,而“$$$\mathtt{codeforceston}$$$”和“$$$\mathtt{z}$$$”则不然。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^6$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的下一行包含长度为 $$$n$$$ 的字符串 $$$s$$$。字符串$$$s$$$由小写英文字母组成。
保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出 $$$s$$$ 的所有重新排列中按字典顺序排列的最小可能核心。
示例
输入 #1
6 3 qaq 4 cccc 6 bazoka 6 zazzzz 7 ababbbb 7 ccbabcc
输出 #1
qaq cccc z zzz bbababb cbcacbc
注意
第一个测试用例中,所有可能的重新排列及其对应的核心如下:
- “$$$\mathtt{qaq}$$$”,其核心是“$$$\mathtt{qaq}$$$”。
- “$$$\mathtt{aqq}$$$”,其核心是“$$$\mathtt{qq}$$$”。
- “$$$\mathtt{qqa}$$$”,其核心是“$$$\mathtt{qqa}$$$”。
所以所有重排方案中字典顺序最小的核心是“$$$\mathtt{qaq}$$$”。