solve this in c++

You have a string s1s2sns1s2sn and you stand on the left of the string looking right. You want to choose an index kk (1kn1kn) and place a mirror after the kk-th letter, so that what you see is s1s2sksksk1s1s1s2sksksk1s1. What is the lexicographically smallest string you can see?

A string aa is lexicographically smaller than a string bb if and only if one of the following holds:

• aa is a prefix of bb, but abab;
• in the first position where aa and bb differ, the string aa has a letter that appears earlier in the alphabet than the corresponding letter in bb.

Input

The first line of input contains one integer tt (1t100001t10000): the number of test cases.

The next tt lines contain the description of the test cases, two lines per a test case.

In the first line you are given one integer nn (1n1051n105): the length of the string.

The second line contains the string ss consisting of nn lowercase English characters.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

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

Example

input

4 10 codeforces 9 cbacbacba 3 aaa 4 bbaa 

output

cc cbaabc aa bb 

Note

In the first test case choose k=1k=1 to obtain "cc".

In the second test case choose k=3k=3 to obtain "cbaabc".

In the third test case choose k=1k=1 to obtain "aa".

In the fourth test case choose k=1k=1 to obtain "bb".