题目描述

有一个由 $\tt B$ 和 $\tt T$ 组成的字符串。

你可以进行如下操作：选择一个长度为 $4$ 的子串，其恰好等于 $\texttt{BTTB}$，并将其修改为 $\texttt{TBBT}$。你可以进行这种操作任意多次（也可以不操作）。

定义一个字符串的权值为最长的 $\texttt{T}$ 连续段长度。你需要通过如上操作使得字符串的权值尽可能大。输出这个最大值。

• 子串的定义：一个字符串 $b$ 被称为字符串 $a$ 的子串，当且仅当可以通过删除 $a$ 开头若干个（可以是 $0$ 个，下同）字符和结尾若干个字符得到 $b$。
• $\texttt{T}$ 连续段的定义：一个原字符串的仅由 $\texttt{T}$ 构成的子串。

输入格式

第一行一个正整数 $T$ 表示数据组数。

接下来每组数据，第一行一个正整数 $n$ 表示字符串长度，第二行一个长度为 $n$ 的字符串 $S$，表示题目中的字符串。

输出格式

$T$ 行，每行一个非负整数，表示最长 $\texttt{T}$ 连续段的长度。

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

3
2
2
1
3
5

提示

本题采用捆绑测试。

记 $\sum n$ 为所有数据中的 $n$ 的和。

• 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）：保证给定的字符串无法进行任何操作。
• Subtask 4（45 pts）：无特殊限制。

对于所有数据，$1 \leq T \leq 10^3$，$1 \leq n \leq 10^5$，$1 \leq \sum n \leq 5\times 10^5$，字符串只包含字符 B 和 T。