String periods

Given a string \(X\) of length \(n\), an integer \(p\) (\(1\leq p < n\)) is called a period length of \(X\) if \(X[i]=X[i+p]\) for all \(i\) for which both \(i\) and \(i+p\) are valid indices into \(X\).

The smallest of \(X\)’s period lengths is called its regularity. If \(X\) has no period lengths, its regularity is \(n\).

For example, the period lengths of abcabcab are 3 and 6, and the period lengths of aabaa are 3 and 4. Hence, the strings abcabcab and aabaa both have regularity 3. The string abcb has no period lengths and therefore its regularity is 4.

Statement

On the ground someone painted \(n\) spots in a row, with exactly 1 step between adjacent spots. There are \(n\) people, one standing on each spot. Each person has a t-shirt with a letter, so together (when we read their t-shirts left to right) they are forming a string. You are given the string \(S\) obtained this way.

The people want to rearrange themselves to produce a new string \(T\) with the smallest possible regularity. Additionally, they want to do this as efficiently as possible.

The rearrangement will be performed as a series of actions. Each action must look as follows:

• Each action consists of one person taking either one step left or one step right.
• After each action, each person must be standing at one of the spots.
• After each action, there can be at most three people standing on each individual spot – the spots aren’t big enough to hold more than three people at the same time.

After the last action the people must again occupy all \(n\) spots, with exactly one person per spot. When read left to right, their t-shirts must produce the desired string \(T\).

Find the smallest possible regularity \(r\) they can achieve this way, and then the smallest possible number \(a\) of actions needed to rearrange the people into some string \(T\) with regularity \(r\).

Input format

The first line of the input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.

Each test case consists of two lines. The first line contains the number \(n\) of people, the second line the string \(S\) initially formed by the letters on their t-shirts.

Each character in each \(S\) will be an uppercase or a lowercase English letter (A-Z, a-z).

Output format

For each test case output a single line of the form “\(r\) \(a\)”.

Subproblem W1 (14 points, public)

Input file: W1.in

In this subproblem \(t\leq 100\) and in each test \(n\leq 10\).

Subproblem W2 (28 points, secret)

Input file: W2.in

In this subproblem \(t\leq 100\) and in each test \(n\leq 100\) and \(r\leq 10\). That is, in this subtask it is guaranteed that each \(S\) was chosen so that there is a corresponding \(T\) with a small regularity.

Subproblem W3 (46 points, secret)

Input file: W3.in

In this subproblem \(t\leq 100\) and in each test \(n\leq 100\).

Subproblem W4 (12 points, secret)

Input file: W4.in

In this subproblem \(t\leq 100\) and in each test \(n\leq 1000\).

Example

6
8
abcabcab
8
abcabcba
8
abcabcac
5
abcdd
10
aaaaabbbbb
4
PQrS

3 0
3 2
3 4
4 6
2 20
4 0

Explanations:

• Test case 1: The input string already has a period length 3 and it is not possible to rearrange it into a string with a shorter period length.
• Test case 2: Last person takes a step left and then the other person standing there takes a step right. This produces the string from the previous test case.
• Test case 3: Two pairs of neighbors can swap places to produce the string acbacbac.
• Test case 4: Produce the string dabcd. (For fun, note that if we weren’t limited to staying in the original \(n\) spots, there would be a faster way to produce this string: the rightmost person could take five steps left.)
• Test case 5: Here the optimal solution is for the people to rearrange themselves to form the string ababababab.
• Test case 6: Like in test case 1, we cannot improve the string’s regularity, so the best solution is to do nothing. Note that both upper- and lowercase letters can appear in the input.