CF1616B Mirror in the String

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.

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".