Description

字符串是个好东西，当你不知道该出什么题的时候，出道字符串的题水一水就好了，从签到题到金牌题，字符串一定能满足你的需求。——某出题人

你现在手上有一个由小写字母构成的字符串s（S1S2S3...Sn），你站在字符串的左端向右看，整个字符串一览无余。现在你希望从字符串中选择一个字符，在这个字符后面放上一面镜子，这样，你看到的字符串就变成了S1S2...SkS(k-1)...S1。现在你希望让自己看到的字符串字典序最小，请你找出这样的字典序最小的字符串。

本题中a字符串的字典序小于b字符串定义如下：

1.a是b的前缀，且a≠b。

2.在a和b字符串中第一个字符不同的位置，a中的字母在字母表中出现的比b中的字母早。

Input Format

第一行包含一个整数t（1≤t≤10000），代表测试样例的数量。

接下来每个测试样例包含两行，第一行包含一个整数n（1≤n≤100000），代表字符串的长度。

第二行为长度为n的字符串s。

保证所有测试样例中的n总和不超过100000。

Output Format

对于每个测试样例，输出字典序最小的字符串。

4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa​

cc
cbaabc
aa
bb​

Source

字符串