E-时锁·封印_牛客挑战赛82

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

【题目背景】
$\hspace{15pt}$ MuQ 成功地战胜了 Papy ！
$\hspace{15pt}$ Papy 满意地点点头：“愿赌服输，我这就兑现承诺。”
$\hspace{15pt}$ 在 Papy 的带领下，他们来到一扇巨大的石门前。
$\hspace{15pt}$ “门后就是你要找的答案，” Papy 拍拍 MuQ 的肩膀，“接下来就看你的了。” 话音未落，Papy 便化作一群萤火虫飞走了。
$\hspace{15pt}$ MuQ 虽然有些不解，但现在最重要的是拯救企鹅文明。
$\hspace{15pt}$ 他仔细检查石门，发现旁边积着厚厚的灰尘。擦干净后，露出了一个石碑。石碑上有一行刻着的文字：
$\hspace{15pt}$ “请输入正确密码开门。密码提示：从下面这个字符串中找出密钥。”

$\hspace{15pt}$ 石碑的底部有一个长度为 $n$ 的字符串 $s$ 。
$\hspace{15pt}$ 石碑上写道，“大门的密钥是 $s$ 中所有的美丽串 $^\texttt{[1]}$ 中，字典序 $^\texttt{[2]}$ 最大的那一个”。
$\hspace{15pt}$ 你能帮助 MuQ 求出这串密钥吗？

【名词解释】本题中涉及到的名称定义如下（字符串下标均从 $0$ 开始）：

$\hspace{15pt}$ 美丽串 $^\texttt{[1]}$ ：任取 $s$ 中的一个非空连续子串 $t$ 。称 $t$ 的所有循环排列 $^\texttt{[3]}$ 中字典序最大的字符串为 $t'$ ，此时 $t'$ 为 $s$ 的一个美丽串。
$\hspace{15pt}$ 字符串的字典序 $^\texttt{[2]}$ 比较：从左到右逐个比较两个字符串的字符。如果在某个位置上字符不同，比较这两个字符的字母表顺序，字母序大的字符串字典序也大。如果一直比较到其中一个字符串结束，则较短的字符串字典序更小。
$\hspace{15pt}$ 循环排列 $^\texttt{[3]}$ ：称字符串 $t$ 是 $s$ 的一种循环排列，当且仅当 $|s| = |t|$ $^\texttt{[4]}$ 并且存在一个整数 $k$ 满足 $0 \le k < |s|$ ，使得 $\forall \ 0 \le i < |s|,s_i = t_{(i+k) \bmod |t|}$ 。
$\hspace{15pt}$ $|s|$ $^\texttt{[4]}$ ：表示字符串 $s$ 的长度。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第二行输入一个整数  代表字符串长度。
第三行输入一个长度为 ，仅由小写英文字母构成的字符串 。
除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行输出一个字符串，表示  的字典序最大的美丽串。

示例1

输入

复制

3
5
bbaba
8
abcabcaa
3
aaa

输出

复制

bbba
ccab
aaa

说明

对于第一组测试数据，其中一种选取方式为：选取子串 ，循环排列后得到 。可以证明不存在字典序更大的答案。

题目描述

输入描述:

输出描述:

输入

输出

说明

备注: