Good Bye 2021: 2022 is NEAR |
---|
Finished |
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:
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.
4 10 codeforces 9 cbacbacba 3 aaa 4 bbaa
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".
Name |
---|