你有一个字符串 $$$s_1 s_2 \ldots s_n$$$ 并且你站在字符串的左边向右看。您想要选择一个索引 $$$k$$$ ($$$1 \le k \le n$$$) 并在第 $$$k$$$ 个字母之后放置一个镜像,这样您看到的就是 $$$s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1$$$。您能看到的按字典顺序最小的字符串是什么?
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。
输入
第一行输入包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$):测试用例的数量。
接下来的 $$$t$$$ 行包含测试用例的描述,每个测试用例两行。
在第一行中,您将获得一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$):字符串的长度。
第二行包含由 $$$n$$$ 小写英文字符组成的字符串 $$$s$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印您可以看到的按字典顺序排列的最小字符串。
示例
输入 #1
4 10 codeforces 9 cbacbacba 3 aaa 4 bbaa
输出 #1
cc cbaabc aa bb
注意
在第一个测试用例中选择 $$$k = 1$$$ 来获取“cc”。
在第二个测试用例中选择 $$$k = 3$$$ 以获得“cbaabc”。
在第三个测试用例中,选择 $$$k = 1$$$ 以获得“aa”。
在第四个测试用例中选择 $$$k = 1$$$ 以获得“bb”。