D3. Rotating Strings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A cyclic shift of size $$$k$$$ of the string $$$$$$s_0, s_1, \dots, s_{n - 1}$$$$$$ is the string $$$$$$s_{n - k}, s_{n - k + 1}, \dots, s_{n - 1}, s_0, s_1, \dots, s_{n - k - 1}$$$$$$ More formally, it is the string $$$t$$$ where $$$t_i = s_{(i - k + n) \text{ mod } n}$$$.

For example, a cyclic shift of size $$$2$$$ of the string abbcd is the string cdabb, and the cyclic shift of size $$$4$$$ of the string abcdefgh is the string efghabcd.

We say that a string $$$t$$$ is $$$k$$$-indifferent if and only if the cyclic shift of size $$$k$$$ of $$$t$$$ is $$$t$$$. That is, if we perform a cyclic shift of size $$$k$$$, we will obtain the same string.

You are given a string $$$s$$$ of size $$$n$$$, find the maximum non-negative integer $$$r$$$ such that $$$r \lt n$$$, and you can reorder the letters (or possibly keep the string the same) of $$$s$$$ to make it $$$r$$$-indifferent.

Input

The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$, the number of test cases.

The first line of each test case consists of one integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the length of the string.

The second line of each test case consists of a string $$$s$$$ of $$$n$$$ lowercase Latin letters.

The sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output one line containing one integer, the maximum non-negative integer $$$r \lt n$$$ such that $$$s$$$ can be reordered to be $$$r$$$-indifferent.

Example
Input
3
5
abcde
12
aaaabbbbcccc
12
aaaaaabbccbb
Output
0
9
6
Note

In the first test case, there is no way to reorder the string to make it $$$r$$$-indifferent for any positive $$$r$$$, and so the answer is $$$0$$$.

In the second test case, we can reorder the letters of the string to make it abcabcabcabc, and so the answer will be $$$9$$$, since when shifting it by $$$9$$$ letters it remains the same. It can be shown that this is the maximum possible.

In the third test case, we can reorder the letters to make it aaabbcaaabbc, and so the answer will be $$$6$$$. It can be shown that this is the maximum possible.