P9574 "TAOI-2" Break Through the Barrier

There is a string consisting of $\texttt{B}$ and $\texttt{T}$. You can perform the following operation: choose a substring of length $4$ that is exactly $\texttt{BTTB}$, and change it to $\texttt{TBBT}$. You may perform this operation any number of times (or not perform it at all). Define the weight of a string as the length of the longest consecutive segment of $\texttt{T}$. You need to make the weight of the string as large as possible using the operation above. Output this maximum value. - Definition of substring: a string $b$ is called a substring of a string $a$ if and only if $b$ can be obtained by deleting some (possibly $0$) characters from the beginning of $a$ and some characters from the end of $a$. - Definition of a consecutive $\texttt{T}$ segment: a substring of the original string that consists only of $\texttt{T}$.

The first line contains a positive integer $T$, indicating the number of test cases. For each test case, the first line contains a positive integer $n$, indicating the length of the string. The second line contains a string $S$ of length $n$, which is the string in this problem.

Output $T$ lines. Each line contains a non-negative integer, representing the length of the longest consecutive segment of $\texttt{T}$.

**This problem uses bundled testdata.** Let $\sum n$ be the sum of $n$ over all test cases. - Subtask 0 (5 pts): $n \leq 7$. - Subtask 1 (20 pts): $T \leq 10$, $n \leq 10$. - Subtask 2 (25 pts): $\sum n \leq 5000$. - Subtask 3 (5 pts): it is guaranteed that the given string cannot perform any operation. - Subtask 4 (45 pts): no special restrictions. For all testdata, $1 \leq T \leq 10^3$, $1 \leq n \leq 10^5$, $1 \leq \sum n \leq 5 \times 10^5$, and the string contains only the characters `B` and `T`. Translated by ChatGPT 5