CF1316B.String Modification

Vasya has a string $s$ of length $n$. He decides to make the following modification to the string:

1. Pick an integer $k$, ($1 \leq k \leq n$).

2. For $i$ from $1$ to $n-k+1$, reverse the substring $s[i:i+k-1]$ of $s$. For example, if string $s$ is qwer and $k = 2$, below is the series of transformations the string goes through:

   • qwer (original string)
   • wqer (after reversing the first substring of length $2$)
   • weqr (after reversing the second substring of length $2$)
   • werq (after reversing the last substring of length $2$)

   Hence, the resulting string after modifying $s$ with $k = 2$ is werq.

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:

• $a$ is a prefix of $b$, but $a \ne b$;
• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

Vasya 有一个长度为 $n$ 的字符串 $s$。他决定对这个字符串进行如下修改：

1. 选择一个整数 $k$（满足 $1 \leq k \leq n$）；

2. 对于每个 $i$ 从 $1$ 到 $n-k+1$，将 $s$ 的子串 $s[i:i+k-1]$ 进行翻转。例如，若字符串 $s$ 为 qwer 且 $k = 2$，则字符串经历以下一系列变换：

   • qwer（原始字符串）
   • wqer（翻转第一个长度为 $2$ 的子串后）
   • weqr（翻转第二个长度为 $2$ 的子串后）
   • werq（翻转最后一个长度为 $2$ 的子串后）

   因此，对 $s$ 使用 $k = 2$ 修改后得到的最终字符串为 werq。

Vasya 希望选出一个 $k$，使得经过上述修改后所得的字符串在所有可能的 $k$ 中字典序最小。在所有能达成该最小字典序的 $k$ 中，他希望选出最小的那个。由于他正忙于参加 Felicity 2020，因此请求你的帮助。

字符串 $a$ 字典序小于字符串 $b$ 当且仅当满足以下条件之一：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀且 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中的字符在字母表中位于 $b$ 中对应字符之前。

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$.

每个测试包含多个测试用例。

第一行包含测试用例的数量 $t$（$1 \le t \le 5000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$）—— 字符串 $s$ 的长度。

每个测试用例的第二行包含由 $n$ 个小写拉丁字母组成的字符串 $s$。

保证所有测试用例的 $n$ 之和不超过 $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.

对于每个测试用例，输出两行：

第一行输出经过上述修改后能得到的字典序最小的字符串 $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$ : baba

  The lexicographically smallest string achievable through modification is abab for $k = 1$ and $3$. Smallest value of $k$ needed to achieve is hence $1$.

在第一个样例的第一个测试用例中，字符串 abab 经过修改后得到的结果如下：

• 当 $k = 1$ 时：abab
• 当 $k = 2$ 时：baba
• 当 $k = 3$ 时：abab
• 当 $k = 4$ 时：baba

通过修改所能得到的字典序最小的字符串是 abab（对应 $k = 1$ 和 $k = 3$）。因此，达到该最小字典序字符串所需的最小 $k$ 值为 $1$。