题目描述

定义 f(x)为字符串 x中不同字符的数量。例如 f("abc")=3、f("TTTTT")=1或 f("TxTyTxTy")=3。

给定一个字符串 s，将它分成两个非空子串 a和 b（即 a + b = s），使得 f(a) + f(b)的值最大，请你计算并求出该最大值。

输入格式

第一行包含一个整数 T，表示输入包含 T组数据。 对于每组数据：

第一行包含一个整数 n，表示字符串 s的长度；

第二行包含一个字符串 s。

保证字符串 s只包含大小写字母和数字字符，且区分大小写。

输出格式

对于每组数据，输出一行，包含一个整数，表示 f(a)+f(b)的最大值，其中 a+b=s。

2
2
aa
7
abcabcd

2
7

数据规模与约定

对于 $60\%$的数据：$1 \le T \le 100$，$2 \le n \le 800$。

对于 $100\%$的数据：$1 \le T \le 10^4$，$2 \le n \le 2 \times 10^5$，保证同一组数据中所有的 $n$之和不超过 $2 \times 10^5$。