题目描述

$f(x)$ 表示字符串 $x$ 包含的不同字符数。例如，$f(abc)=3$，$f(bbbbb)=1$，$f(babacaba)=3$。

给定一个字符串 $s$，将其拆分为两个非空字符串 $a$ 和 $b$，使得 $f(a)+f(b)$ 最大。（字符串 $a$ 和字符串 $b$ 的串联等于字符串 $s$）。

输入格式

输入由多个测试用例组成。第一行包含整数 $t(1≤t≤10^4)$ 代表测试用例数。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $n(2≤n≤2\times 10^5)$ 代表字符串的长度。

第二行包含字符串 $s$，由小写英文字母组成。

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每个测试用例，输出 $f(a)+f(b)$的最大可能值。

测试样例

5
2
aa
7
abcabcd
5
aaaaa
10
paiumoment
4
aazz

2
7
2
10
3

样例说明

对于第一个测试用例，只有一种有效的方法可以将 aa 拆分为两个非空字符串 a 和 a，并且 $f(a)+f(a)=1+1=2$。

对于第二个测试用例，通过将 abcabcd 分解为 abc 和 abcd，我们可以得到 $f(abc)+f(abcd)=3+4=7$ ，这是最大的。

对于第三个测试用例，无论我们如何拆分字符串，答案总是 $2$。