让我们将字符串 $$$x$$$ 的 $$$f(x)$$$ 函数表示为该字符串包含的不同字符的数量。例如 $$$f(\texttt{abc}) = 3$$$、$$$f(\texttt{bbbbb}) = 1$$$ 和 $$$f(\texttt{babacaba}) = 3$$$。
给定一个字符串 $$$s$$$,将其拆分为两个非空字符串 $$$a$$$ 和 $$$b$$$,使得 $$$f(a) + f(b)$$$ 是可能的最大值。换句话说,找到 $$$f(a) + f(b)$$$ 的最大可能值,使得 $$$a + b = s$$$ (字符串 $$$a$$$ 和字符串 $$$b$$$ 的串联等于字符串 $$$s$$$)。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$) — 字符串 $$$s$$$ 的长度。
第二行包含字符串$$$s$$$,由小写英文字母组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot10^5$$$。
输出
对于每个测试用例,输出一个整数 - $$$f(a) + f(b)$$$ 的最大可能值,使得 $$$a + b = s$$$。
示例
输入 #1
5 2 aa 7 abcabcd 5 aaaaa 10 paiumoment 4 aazz
输出 #1
2 7 2 10 3
注意
对于第一个测试用例,只有一种有效方法可以将 $$$\texttt{aa}$$$ 拆分为两个非空字符串 $$$\texttt{a}$$$ 和 $$$\texttt{a}$$$,以及 $$$f(\texttt{a}) + f(\texttt{a}) = 1 + 1 = 2$$$。
对于第二个测试用例,通过将 $$$\texttt{abcabcd}$$$ 拆分为 $$$\texttt{abc}$$$ 和 $$$\texttt{abcd}$$$,我们可以得到 $$$f(\texttt{abc}) + f(\texttt{abcd}) = 3 + 4 = 7$$$ 的答案,这是最大可能的答案。
对于第三个测试用例,无论我们如何分割字符串,答案总是 $$$2$$$。