Problem Description

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}$.

Input Format

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 Format

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

6
3
TTT
4
BTTB
5
TBBTT
6
BTBTBB
7
BTTBTTB
17
TTBTBTTBTBTTTBTTB

3
2
2
1
3
5

Hint

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