CF2238E Cake Trial

> 蛋糕是一个谎言。 > ——《传送门》 光圈科技 enrichment center 的人工智能 GLaDOS 决定为 Chell 安排另一项测试。这次测试与蛋糕有关。 GLaDOS 将 $n$ 块蛋糕排成一排。每块蛋糕可以是真实的（T）或虚假的（F）。Chell 必须猜测哪些蛋糕是真实的，哪些是虚假的。Chell 有一种独特的能力：她只需看一眼就能确定一块蛋糕是否真实。然而，在她的回答中，她必须满足 GLaDOS 的奇怪条件：Chell 回答中所有虚假的蛋糕必须形成一个连续子段（可能为空）。 最初，GLaDOS 准备了一些蛋糕的排列，但有些蛋糕尚未放置。给定一个长度为 $n$ 的字符串 $s$，描述当前状况： - 如果 $s_i = \texttt{T}$，则第 $i$ 块蛋糕是真实的； - 如果 $s_i = \texttt{F}$，则第 $i$ 块蛋糕是虚假的； - 如果 $s_i = \texttt{N}$，则第 $i$ 个位置尚未放置蛋糕，GLaDOS 可以自行决定在那里放置真实或虚假的蛋糕。 在 GLaDOS 完成排列（将所有 $\texttt{N}$ 替换为 $\texttt{T}$ 或 $\texttt{F}$）之后，Chell 将看到最终排列，并且确切知道每块蛋糕是真实还是虚假。Chell 将选择一个连续区间 $[l, r]$（$1 \le l \le r \le n$），她声明该区间内的蛋糕为虚假蛋糕（或者她可以声明所有蛋糕都是真实的）。区间外的所有蛋糕都被视为真实的。Chell 希望她的答案尽可能接近真实情况，因此她会选择区间使得错误数量最小。 GLaDOS 很狡猾，她想让 Chell 更难。她希望放置剩余的蛋糕（将所有 $\texttt{N}$ 替换为 $\texttt{T}$ 或 $\texttt{F}$），使得在 Chell 最优选择区间的情况下，Chell 被迫犯下的错误数量尽可能大。 请帮助 GLaDOS 确定她能保证的最大错误数量。

每个测试点包含多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 500$）——蛋糕的数量。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{T}$、$\texttt{F}$、$\texttt{N}$ 组成——当前蛋糕的排列。 保证所有测试用例的 $n^3$ 之和不超过 $500^3$。

对于每个测试用例，输出一个整数 —— GLaDOS 能保证的最大错误数量。

在第一个测试用例中，$s = \texttt{FTFF}$，所有蛋糕都已放置。Chell 会选择区间 $[3,4]$，得到答案 $\texttt{TTFF}$，她会犯 $1$ 个错误。 在第二个测试用例中，$s = \texttt{TNFTT}$，有 $1$ 块蛋糕未放置。无论将 $\texttt{N}$ 替换为 $\texttt{T}$ 还是 $\texttt{F}$，假蛋糕都形成一个连续区间，Chell 可以选择它，因此答案是 $0$。 在第三个测试用例中，$s = \texttt{TFTTTN}$，GLaDOS 会将 $\texttt{N}$ 替换为 $\texttt{F}$，得到 $\texttt{TFTTTF}$。可以证明答案至少为 $1$。如果 Chell 选择区间 $[2,2]$，即给出答案 $\texttt{TFTTTT}$，她恰好会犯 $1$ 个错误。 在第四个测试用例中，$s = \texttt{TNNFTF}$，GLaDOS 会将蛋糕排列为 $\texttt{TFTFTF}$。Chell 会选择区间 $[2,4]$（答案：$\texttt{TFFFTT}$），犯 $2$ 个错误。 翻译由 DeepSeek 生成。