Mirror in the String

题意翻译

给定一个字符串，你可以在第 k 个字符后面放一面镜子，这样这个字符串就会变成 $ s_1s_2s_3...s_{k-1}s_ks_{k-1}...s_3s_2s_1 $ 这种形式。问你放完镜子后能看到的字典序最小的字符串。 a 的字典序比 b 小，满足： - a 是 b 的前缀且 $ a \neq b $ - a 第一个与 b 对应位置不同的字符在字母表中比对应 b 的字符先出现。

题目描述

You have a string $ s_1 s_2 \ldots s_n $ and you stand on the left of the string looking right. You want to choose an index $ k $ ( $ 1 \le k \le n $ ) and place a mirror after the $ k $ -th letter, so that what you see is $ s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1 $ . What is the lexicographically smallest string you can see? A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

输入输出格式

输入格式

The first line of input contains one integer $ t $ ( $ 1 \leq t \leq 10\,000 $ ): the number of test cases. The next $ t $ lines contain the description of the test cases, two lines per a test case. In the first line you are given one integer $ n $ ( $ 1 \leq n \leq 10^5 $ ): the length of the string. The second line contains the string $ s $ consisting of $ n $ lowercase English characters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print the lexicographically smallest string you can see.

输入输出样例

输入样例 #1

4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa

输出样例 #1

cc
cbaabc
aa
bb

说明

In the first test case choose $ k = 1 $ to obtain "cc". In the second test case choose $ k = 3 $ to obtain "cbaabc". In the third test case choose $ k = 1 $ to obtain "aa". In the fourth test case choose $ k = 1 $ to obtain "bb".