Distinct Split

Description:

Input:

The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — the length of the string $$$s$$$.

The second line contains the string $$$s$$$, consisting of lowercase English letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output:

For each test case, output a single integer  — the maximum possible value of $$$f(a) + f(b)$$$ such that $$$a + b = s$$$.

Sample Input:

5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz

Sample Output:

2
7
2
10
3

Note:

For the first test case, there is only one valid way to split $$$\texttt{aa}$$$ into two non-empty strings $$$\texttt{a}$$$ and $$$\texttt{a}$$$, and $$$f(\texttt{a}) + f(\texttt{a}) = 1 + 1 = 2$$$.

For the second test case, by splitting $$$\texttt{abcabcd}$$$ into $$$\texttt{abc}$$$ and $$$\texttt{abcd}$$$ we can get the answer of $$$f(\texttt{abc}) + f(\texttt{abcd}) = 3 + 4 = 7$$$ which is maximum possible.

For the third test case, it doesn't matter how we split the string, the answer will always be $$$2$$$.