题目描述

给你一个仅由小写字母组成的字符串 $s$。

一个字符串序列 $t_1, t_2, \ldots, t_k$ 是合法的当且仅当：

• $s = t_1 + t_2 + \cdots + t_k$，此处 $+$ 为字符串拼接；
• $\forall 1 \le i \le k - 1, t_i \ne t_{i + 1}$。

求合法的字符串序列的长度的最大值。

输入格式

本题有多组测试数据。

第一行输入一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含一个正整数 $n$，表示字符串的长度。

第二行包含一个长度为 $n$ 的仅由小写字母组成的字符串 $s$。

输出格式

对于每组数据，输出一行一个整数，表示合法的字符串序列的长度的最大值。

4
3
abc
5
aabbb
6
aaaaaa
10
pppqqppppq

3
3
4
7

提示

【样例解释】

在第一组数据中，一个合法且长度最大的字符串序列为 $[\texttt{a}, \texttt{b}, \texttt{c}]$。

在第二组数据中，一个合法且长度最大的字符串序列为 $[\texttt{a}, \texttt{abb}, \texttt{b}]$。

在第三组数据中，一个合法且长度最大的字符串序列为 $[\texttt{a}, \texttt{aa}, \texttt{a}, \texttt{aa}]$。

【数据范围】

本题采用捆绑测试且开启子任务依赖。

对于所有数据，满足 $1 \le T \le 10^5$，$1 \le n, \sum n \le 10^6$，$s$ 仅由小写字母组成。