D-Poi 的消消乐_牛客小白月赛116

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ Poi 带着 $n$ 个石头，第 $i$ 个石头被涂上颜色 $c_i$ ，且不同颜色的数量至多为两种。
$\hspace{15pt}$ Poi 背石头背的非常累，于是 Poi 打算对石头进行压缩。具体地，Poi 每次可以选择四个整数 $i,j,k,l$ ，如果它们满足：
$\hspace{23pt}\bullet\,0 \le i \le j \lt k \le l \lt n$ 且 $j+1=k$ ；
$\hspace{23pt}\bullet\,0\le i \times j,k \times l\lt n$ 且 $c_{i \times j}=c_{k \times l}$ （石头的序号从 $0$ 开始）。
$\hspace{15pt}$ Poi 就可以从序号为 $i \times j$ 和 $k \times l$ 的石头中选择一块，将它压缩进另一块石头中。其余石头按照原有顺序从前到后依次拼接，同时从 $0$ 开始重新编号。整个过程中，每一块石头的颜色都保持不变。

$\hspace{15pt}$ Poi 可以无限次使用压缩操作，他想要知道，他能将石头压缩到的最小数量是多少。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：
第一行输入一个整数 ，代表石头数量。 
第二行输入一个长度为  的，仅由大写字母构成的字符串 ，其中，第  个字符  代表第  个石头的颜色。保证字符串  中至多包含两种大写字母。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每一组测试数据，新起一行。输出一个整数，代表 Poi 能将石头压缩到的最小数量。

示例1

输入

复制

2
2
AB
3
AAA

输出

复制

2
1