题目描述

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

你需要将 $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}$）。

求满足条件的切分方案中 $k$ 的最大值。

输入格式

本题有多组测试数据。

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

对于每组测试数据：

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

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

输出格式

对于每组数据，输出一行一个整数，表示合法切分方案中子串个数的最大值。

样例

4
3
abc
5
aabbb
6
aaaaaa
10
pppqqppppq

3
3
4
7

提示

【样例解释】

在第一组数据中，一种最优切分为 $[\texttt{a}, \texttt{b}, \texttt{c}]$，共 $3$ 个子串。

在第二组数据中，一种最优切分为 $[\texttt{a}, \texttt{abb}, \texttt{b}]$，共 $3$ 个子串。

在第三组数据中，一种最优切分为 $[\texttt{a}, \texttt{aa}, \texttt{a}, \texttt{aa}]$，共 $4$ 个子串。

【数据范围】

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

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