Background

Original problem link: https://oier.team/problems/J2C.

Problem Description

You are given a string $s$ consisting only of lowercase letters.

A sequence of strings $t_1, t_2, \ldots, t_k$ is valid if and only if:

• $s = t_1 + t_2 + \cdots + t_k$, where $+$ means string concatenation.
• $\forall 1 \le i \le k - 1, t_i \ne t_{i + 1}$.

Find the maximum possible length $k$ of a valid string sequence.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains a positive integer $n$, the length of the string.

The second line contains a string $s$ of length $n$ consisting only of lowercase letters.

Output Format

For each test case, output one line containing an integer, representing the maximum length of a valid string sequence.

4
3
abc
5
aabbb
6
aaaaaa
10
pppqqppppq

3
3
4
7

Hint

Sample Explanation

In the first test case, a valid sequence with maximum length is $[\texttt{a}, \texttt{b}, \texttt{c}]$.

In the second test case, a valid sequence with maximum length is $[\texttt{a}, \texttt{abb}, \texttt{b}]$.

In the third test case, a valid sequence with maximum length is $[\texttt{a}, \texttt{aa}, \texttt{a}, \texttt{aa}]$.

Constraints

This problem uses bundled testdata and enables subtask dependencies.

For all testdata, $1 \le T \le 10^5$, $1 \le n, \sum n \le 10^6$, and $s$ consists only of lowercase letters.

Translated by ChatGPT 5