|CodeCraft-20 (Div. 2)|
Vasya has a string $$$s$$$ of length $$$n$$$. He decides to make the following modification to the string:
Vasya wants to choose a $$$k$$$ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $$$k$$$. Among all such $$$k$$$, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
Each test contains multiple test cases.
The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of the string $$$s$$$.
The second line of each test case contains the string $$$s$$$ of $$$n$$$ lowercase latin letters.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.
For each testcase output two lines:
In the first line output the lexicographically smallest string $$$s'$$$ achievable after the above-mentioned modification.
In the second line output the appropriate value of $$$k$$$ ($$$1 \leq k \leq n$$$) that you chose for performing the modification. If there are multiple values of $$$k$$$ that give the lexicographically smallest string, output the smallest value of $$$k$$$ among them.
6 4 abab 6 qwerty 5 aaaaa 6 alaska 9 lfpbavjsm 1 p
abab 1 ertyqw 3 aaaaa 1 aksala 6 avjsmbpfl 5 p 1
In the first testcase of the first sample, the string modification results for the sample abab are as follows :
The lexicographically smallest string achievable through modification is abab for $$$k = 1$$$ and $$$3$$$. Smallest value of $$$k$$$ needed to achieve is hence $$$1$$$.