P9574 「TAOI-2」Break Through the Barrier

有一个由 $\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}$ 连续段的长度。

**本题采用捆绑测试。** 记 $\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`。