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

你有一个字符串 $s_1 s_2 \ldots s_n$，你站在该字符串的左侧，面朝右侧。你需要选择一个下标 $k$（$1 \le k \le n$），并在第 $k$ 个字母之后放置一面镜子，使得你所看到的字符串为 $s_1 s_2 \ldots s_k s_k s_{k - 1} \ldots s_1$。你能看到的字典序最小的字符串是什么？

当且仅当满足以下条件之一时，字符串 $a$ 的字典序小于字符串 $b$：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀，但 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中对应位置的字母在字母表中早于 $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$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$）：测试用例的数量。

接下来的 $t$ 行描述了各测试用例，每个测试用例占两行。

第一行给出一个整数 $n$（$1 \leq n \leq 10^5$）：字符串的长度。

第二行包含字符串 $s$，由 $n$ 个小写英文字母组成。

保证所有测试用例的 $n$ 值之和不超过 $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".

在第一个测试用例中，选择 $k = 1$，得到字符串 "cc"。

在第二个测试用例中，选择 $k = 3$，得到字符串 "cbaabc"。

在第三个测试用例中，选择 $k = 1$，得到字符串 "aa"。

在第四个测试用例中，选择 $k = 1$，得到字符串 "bb"。