CF1616B Mirror in the String

你有一个字符串 $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 \ne b$； - 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10\,000$），表示测试用例的数量。 接下来的 $t$ 组，每组包含两行。 第一行给出一个整数 $n$（$1 \leq n \leq 10^5$），表示字符串的长度。 第二行包含一个由 $n$ 个小写英文字母组成的字符串 $s$。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出你能看到的字典序最小的字符串。

- 第一个测试用例选择 $k=1$，得到 "cc"。 - 第二个测试用例选择 $k=3$，得到 "cbaabc"。 - 第三个测试用例选择 $k=1$，得到 "aa"。 - 第四个测试用例选择 $k=1$，得到 "bb"。 由 ChatGPT 4.1 翻译