Vasya 有一个长度为 $$$n$$$ 的字符串 $$$s$$$。他决定对字符串进行以下修改:
1. 选择一个整数 $$$k$$$, ($$$1 \leq k \leq n$$$)。
2. 对于从$$$1$$$到$$$n-k+1$$$的$$$i$$$,反转$$$s$$$的子串$$$s[i:i+k-1]$$$。例如,如果字符串 $$$s$$$ 为 qwer 并且 $$$k = 2$$$,则该字符串经历的一系列转换如下: qwer(原始字符串) wqer(反转长度为 $$$2$$$ 的第一个子字符串后) weqr(反转长度为 $$$2$$$ 的第二个子字符串后) werq(反转长度为 $$$2$$$ 的最后一个子字符串后)用 $$$k = 2$$$ 修改 $$$s$$$ 后的字符串是 werq。
Vasya想要选择一个$$$k$$$,使得经过上述修改后获得的字符串在$$$k$$$的所有选择中按字典顺序尽可能最小。在所有这些$$$k$$$中,他想选择最小的一个。由于他正忙于参加 Felicity 2020,他请求您的帮助。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
输入
每个测试包含多个测试用例。
第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 字符串 $$$s$$$ 的长度。
每个测试用例的第二行包含 $$$s$$$ 由 $$$n$$$ 小写拉丁字母组成的字符串。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例输出两行:
在第一行中输出经过上述修改后可实现的字典顺序最小的字符串 $$$s'$$$。
在第二行中输出您选择用于执行修改的 $$$k$$$ ($$$1 \leq k \leq n$$$) 的适当值。如果 $$$k$$$ 的多个值给出了字典顺序最小的字符串,则输出其中 $$$k$$$ 的最小值。
示例
输入 #1
6 4 abab 6 qwerty 5 aaaaa 6 alaska 9 lfpbavjsm 1 p
输出 #1
abab 1 ertyqw 3 aaaaa 1 aksala 6 avjsmbpfl 5 p 1
注意
在第一个样本的第一个测试用例中,样本abab的字符串修改结果如下:
- $$$k = 1$$$ : abab
- $$$k = 2$$$ : 巴巴
- $$$k = 3$$$ : abab
- 对于 $$$k = 4$$$ : baba 对于 $$$k = 1$$$ 和 $$$3$$$,通过修改可实现的字典顺序最小的字符串是 abab。因此,需要实现的 $$$k$$$ 的最小值是 $$$1$$$。