Codeforces Round 849 (Div. 4) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

greedy

strings

*1000

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Distinct Split

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLet's denote the $$$f(x)$$$ function for a string $$$x$$$ as the number of distinct characters that the string contains. For example $$$f(\texttt{abc}) = 3$$$, $$$f(\texttt{bbbbb}) = 1$$$, and $$$f(\texttt{babacaba}) = 3$$$.

Given a string $$$s$$$, split it into two non-empty strings $$$a$$$ and $$$b$$$ such that $$$f(a) + f(b)$$$ is the maximum possible. In other words, find the maximum possible value of $$$f(a) + f(b)$$$ such that $$$a + b = s$$$ (the concatenation of string $$$a$$$ and string $$$b$$$ is equal to string $$$s$$$).

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

Example

Input

52aa7abcabcd5aaaaa10paiumoment4aazz

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/19/2024 18:12:08 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|