#P0856. 最小Move串

最小Move串

题目描述

小明有一个长度为 nn 的字符串 ss,对于每个位置 i (1≤i≤n)i\ (1 \leq i \leq n),他定义 Move(i)Move(i) 为:把第 ii 个字符提到最前面,其余字符按原顺序依次排列接在后面的结果。

例如对于 s="abcd",Move(2)="bacd",Move(4)="dabc"s = "abcd", Move(2) = "bacd", Move(4) = "dabc"。

现在小明想知道,对于 ii 从 11 到 nn,字典序最小的 Move(i)Move(i) 串是什么,请你帮他求一求吧。

输入格式

每个测试文件内都包含多组测试数据。

第一行一个正整数 T (1≤T≤100)T\ (1 \leq T \leq 100),表示测试数据的组数。

接下来对于每组测试数据,输入包含两行。

第一行一个正整数 n (1≤n≤103)n\ (1 \le n \leq 10^3),表示字符串 ss的长度。
第二行一个长度为nn 的字符串 ss。(保证 ss 只由小写字母构成。)

(保证同一文件的测试数据中,nn 的总和不超过 10310^3。)

输出格式

输出包含 TT 行,每行一个长度为 nn 的字符串,表示当前测试用例的最小字典序 MoveMove 串。

样例

4
5
cbaca
8
jsigosfg
8
nowcoder
3
aaa
acbac
fjsigosg
cnowoder
aaa