题目描述

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

给定一个字符串 s，将它分成两个非空子串 a 和 b，使得 f(a)+f(b) 是可能的最大值，请你计算该最大值。

输入格式

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

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

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

输出格式

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

2
2
aa
7
abcabcd

2
7

提示

3
2
aa
2
ab
2
AA

2
2
2

5
3
Txx
5
xxxyX
9
00230abca
6
TTTTTT
4
0a0a

3
4
7
2
4

数据范围

对 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}$。