题目描述

你有一个字符串 $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 翻译

样例

4
10
codeforces
9
cbacbacba
3
aaa
4
bbaa

cc
cbaabc
aa
bb