CF2238E.Cake Trial

The cake is a lie.

— Portal

GLaDOS, the artificial intelligence of the Aperture Science Enrichment Center, decided to conduct another test for Chell. This time, the test is about cakes.

GLaDOS arranged $n$ cakes in a row. Each cake can be either real (T) or fake (F). Chell must guess which cakes are real and which are fake. Chell has a unique ability: she can determine exactly whether a cake is real just by looking at it. However, in her answer, she must satisfy GLaDOS's strange condition: all fake cakes in Chell's answer must form one contiguous subsegment (possibly empty).

Initially, GLaDOS prepared some arrangement of cakes, but some cakes have not been placed yet. You are given a string $s$ of length $n$ describing the current situation:

• $s_i =$ T, if the $i$-th cake is real;
• $s_i =$ F, if the $i$-th cake is fake;
• $s_i =$ N, if there is no cake at the $i$-th position yet, and GLaDOS may still place either a real or a fake cake there at her discretion.

After GLaDOS finishes the arrangement (replaces all N with T or F), Chell will see the final arrangement and will know exactly for each cake whether it is real or fake. Chell will choose a contiguous segment $[l, r]$ ($1 \le l \le r \le n$) that she will declare to be the set of fake cakes (or she may declare all cakes to be real). All cakes outside this segment are considered real. Chell wants her answer to be as close to the truth as possible, so she will choose the segment to minimize the number of mistakes.

GLaDOS, being cunning, wants to make Chell's life harder. She wants to place the remaining cakes (replace all N with T or F) so that the number of mistakes Chell is forced to make, under her optimal choice of segment, is as large as possible.

Help GLaDOS determine the maximum number of mistakes she can guarantee.

蛋糕是个谎言。

——《传送门》

光圈科学丰富中心的人工智能 GLaDOS 决定为雪儿（Chell）开展另一项测试。本次测试的主题是蛋糕。

GLaDOS 将 $n$ 个蛋糕排成一列。每个蛋糕要么是真实的（T），要么是虚假的（F）。雪儿必须猜出哪些蛋糕是真实的，哪些是虚假的。雪儿拥有一种独特的能力：她仅凭观察就能准确判断某个蛋糕是否真实。然而，在她的回答中，她必须满足 GLaDOS 的一项奇怪条件：她在答案中标记为虚假的所有蛋糕必须构成一个连续的子段（该子段可能为空）。

最初，GLaDOS 已准备好了某种蛋糕排列，但其中一些位置尚未放置蛋糕。你将得到一个长度为 $n$ 的字符串 $s$，用于描述当前状态：

• $s_i =$ T，表示第 $i$ 个位置上的蛋糕是真实的；
• $s_i =$ F，表示第 $i$ 个位置上的蛋糕是虚假的；
• $s_i =$ N，表示第 $i$ 个位置上尚未放置蛋糕，GLaDOS 可自由选择在此处放置真实蛋糕（T）或虚假蛋糕（F）。

在 GLaDOS 完成布置（即把所有 N 替换为 T 或 F）后，雪儿将看到最终的排列，并能准确知晓每个蛋糕的真实或虚假状态。随后，雪儿会选择一个连续区间 $[l, r]$（其中 $1 \le l \le r \le n$），并声明该区间内所有蛋糕均为虚假蛋糕（她也可能声明所有蛋糕均为真实蛋糕，即该区间为空）。区间外的所有蛋糕则被视为真实蛋糕。雪儿希望自己的回答尽可能接近真相，因此她将选择使错误数最小的区间。

而狡猾的 GLaDOS 则想让雪儿的日子更难熬。她希望以某种方式放置剩余的蛋糕（即把所有 N 替换为 T 或 F），使得雪儿在最优选择区间的情况下，所犯的错误数尽可能大。

请帮助 GLaDOS 确定她所能保证的最大错误数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 500$) — the number of cakes.

The second line of each test case contains a string $s$ of length $n$ consisting of the characters T, F, or N — the current arrangement of cakes.

It is guaranteed that the sum of $n^3$ over all test cases does not exceed $500^3$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 500$）——蛋糕的数量。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 T、F 或 N 组成——表示蛋糕当前的排列。

保证所有测试用例中 $n^3$ 的总和不超过 $500^3$。

For each test case, output one integer — the maximum number of mistakes that GLaDOS can guarantee.

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

In the first test case, $s =$ FTFF, all cakes are already placed. Chell will choose the segment $[3, 4]$, resulting in the answer TTFF, and she will have $1$ error.

In the second test case, $s =$ TNFTT, $1$ cake is not placed. For any replacement of N with T or F, the fake cakes form a continuous segment that Chell can choose, so the answer is $0$.

In the third test case, $s =$ TFTTTN, GLaDOS will replace N with F, obtaining TFTTTF. It can be shown that the answer is at least $1$. If Chell chooses the segment $[2, 2]$, i.e., gives the answer TFTTTT, she will make exactly $1$ error.

In the fourth test case, $s =$ TNNFTF, GLaDOS will arrange the cakes as follows: TFTFTF. Chell will choose the segment $[2, 4]$ (answer: TFFFTT), making $2$ errors.

在第一个测试用例中，$s =$ FTFF，所有蛋糕均已放置完毕。雪儿将选择区间 $[3, 4]$，得到结果 TTFF，此时她将产生 $1$ 次错误。

在第二个测试用例中，$s =$ TNFTT，有 $1$ 个蛋糕尚未放置。无论将 N 替换为 T 还是 F，假蛋糕都将构成一个连续区间，雪儿均可选择该区间，因此答案为 $0$。

在第三个测试用例中，$s =$ TFTTTN，GLaDOS 将把 N 替换为 F，得到 TFTTTF。可以证明答案至少为 $1$。若雪儿选择区间 $[2, 2]$（即回答 TFTTTT），她将恰好产生 $1$ 次错误。

在第四个测试用例中，$s =$ TNNFTF，GLaDOS 将按如下方式摆放蛋糕：TFTFTF。雪儿将选择区间 $[2, 4]$（答案为 TFFFTT），产生 $2$ 次错误。