题目：不同的分割

每个测试的时间限制： 2 秒 ⏳ 内存限制： 256 兆字节 💾

我们用 f(x) 函数表示字符串 x 中包含的不同字符的数量。例如，f(abc)=3，f(bbbbb)=1，f(babacaba)=3。

给定一个字符串 s，将其分割成两个非空字符串 a 和 b，使得 f(a)+f(b) 尽可能大。换句话说，找到使得 f(a)+f(b) 最大的可能值，使得 a+b=s（字符串 a 和字符串 b 的连接等于字符串 s）。

输入

输入由多个测试用例组成。第一行包含一个整数 t（1≤t≤104）——测试用例的数量。🌟

每个测试用例的第一行包含一个整数 n（2≤n≤2⋅105）——字符串 s 的长度。

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

保证所有测试用例的 n 之和不超过 2⋅105。

输出

对于每个测试用例，输出一个整数——使得 a+b=s 的 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。 😊📚