CF1316B String Modification

Vasya 有一个长度为 $n$ 的字符串 $s$。他想要对它进行以下的修改： 1. 选择一个整数 $k$ 且 $1\leq k\leq n$。 2. 让 $i$ 从 $1$ 循环到 $n - k + 1$，每一次反转 $s$ 在 $[i,i + k - 1]$ 范围中的子串。 比如说，字符串 $s$ 是 $\texttt{qwer}$ 且 $k = 2$，以下就是 $s$ 被修改的过程： - $\texttt{qwer}$（原字符串） - $\texttt{wqer}$（旋转了第一个长为 $2$ 的子串） - $\texttt{weqr}$（旋转了第二个长为 $2$ 的子串） - $\texttt{werq}$（旋转了最后一个长为 $2$ 的子串） 所以，$s$ 经过 $k = 2$ 的一系列变化后最终会变成 $\texttt{werq}$。 Vasya 希望选择一个 $k$,使得经过上述变化的字符串字典序最小。如果多个不同的 $k$ 都能满足要求，他想要取最小的一个。他正忙着参加 Felicity 2020，于是他叫你来帮他。 一个字符串 $a$ 比 $b$ 字典序更小需要以下条件中只有一个满足： - $a$ 是 $b$ 的前缀，但 $a \ne b$; - 在从左往右 $a$ 和 $b$ 第一个不同的位置，$a$ 上的字符在字母表中比 $b$ 上字符更靠前。

每一个测试点有多组数据。 第一行有一个整数 $t(1\leq t\leq 5000)$ 表示数据组数。 每组数据第一行包含一个整数 $n$，表示字符串长度。 第二行包含一个有 $n$ 个小写英文字母的字符串 $s$。 保证每组数据的 $n$ 不会超过 $5000$。

对于每一组数据打印两行： 第一行是可以达到的字典序最小的字符串 $s'$。 第二行是与之相应的 $k(1\leq k\leq n)$ 用来进行修改。如果多个 $k$ 都可以达到字典序最小的字符串，请打印最小的一个 $k$。

In the first testcase of the first sample, the string modification results for the sample abab are as follows : - for $ k = 1 $ : abab - for $ k = 2 $ : baba - for $ k = 3 $ : abab - for $ k = 4 $ : babaThe lexicographically smallest string achievable through modification is abab for $ k = 1 $ and $ 3 $ . Smallest value of $ k $ needed to achieve is hence $ 1 $ .