Mirror in the String
Description
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.
Input
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$.
Output
For each test case print the lexicographically smallest string you can see.
Samples
4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa
cc
cbaabc
aa
bb
Note
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".