P10841 [MX-J2-T2] Turtle and Strings

Original problem link: .

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.

**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.

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

#### 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.** | Subtask ID | Score | $n \le$ | $\sum n \le$ | Special Property | Subtask Dependencies | | :-: | :-: | :-: | :-: | :-: | :-: | | $1$ | $18$ | $9$ | $10^4$ | None | None | | $2$ | $21$ | $50$ | $10^3$ | None | $1$ | | $3$ | $12$ | $10^6$ | $10^6$ | $s_1 = s_2 = \cdots = s_n$ | None | | $4$ | $23$ | $10^6$ | $10^6$ | There exists **exactly** one position $1 \le i \le n - 1$ such that $s_i \ne s_{i + 1}$ | None | | $5$ | $26$ | $10^6$ | $10^6$ | None | $1, 2, 3, 4$ | 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