← 返回题目列表

Codeforces · 2238/E

E. 蛋糕试用

中文机器翻译题面 查看原题

蛋糕是个谎言。
— 门户

Aperture科学浓缩中心的人工智能GLaDOS决定对Chell进行另一次测试。这次的测试是关于蛋糕的。

GLaDOS 将 $$$n$$$ 蛋糕排成一排。每个蛋糕可以是真实的(T)或假(F)。切尔必须猜出哪些蛋糕是真的,哪些是假的。切尔有一种独特的能力:她只需看一眼就能准确判断蛋糕的真假。然而,在她的答案中,她必须满足 GLaDOS 的奇怪条件:Chell 答案中的所有假蛋糕必须形成一个连续的子段(可能是空的)。

最初,GLaDOS准备了一些蛋糕的排列,但有些蛋糕尚未放置。给你一个长度为 $$$n$$$ 的字符串 $$$s$$$ 描述当前情况:

  • $$$s_i =$$$ T,如果第 $$$i$$$ 个蛋糕是真的;
  • $$$s_i =$$$ F,如果第 $$$i$$$ 个蛋糕是假的;
  • $$$s_i =$$$ N,如果第 $$$i$$$ 位置还没有蛋糕,GLaDOS 仍然可以自行决定在那里放置一个真实的或假的蛋糕。
GLaDOS 完成排列后(替换所有 N 与 T or F),Chell将看到最终的安排,并准确地知道每个蛋糕是真的还是假的。 Chell 将选择一个连续的段 $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$),她将声明它是一组假蛋糕(或者她可以声明所有蛋糕都是真实的)。该部分之外的所有蛋糕都被认为是真实的。 Chell希望她的答案尽可能接近事实,所以她会选择尽量减少错误的部分。

狡猾的 GLaDOS 想让 Chell 的生活变得更加艰难。她想把剩下的蛋糕(全部替换掉) N 与 T or F)使得Chell在她的最优选择下被迫犯的错误数量尽可能大。

帮助 GLaDOS 确定她可以保证的最大错误数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

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

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

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

输出

对于每个测试用例,输出一个整数——GLaDOS 可以保证的最大错误数。

示例

输入
复制

10
4
FTFF
5
TNFTT
6
TFTTTN
6
TNNFTF
7
TNFNTNF
6
NNFFNN
7
TNTFNTN
1
N
5
NNNNN
10
NNNTTNNNFN

输出
复制

1
0
1
2
2
2
2
0
2
3

注意

在第一个测试用例中,$$$s =$$$ FTFF,所有蛋糕已经摆好。 Chell 将选择 $$$[3, 4]$$$ 段,得出答案 TTFF,她将出现 $$$1$$$ 错误。

在第二个测试用例中,$$$s =$$$ TNFTT,$$$1$$$ 蛋糕未放置。对于任何更换 N 与 T or F,假蛋糕形成了 Chell 可以选择的连续线段,所以答案是 $$$0$$$。

在第三个测试用例中,$$$s =$$$ TFTTTN,GLaDOS 将取代 N 与 F,获得 TFTTTF。可以证明答案至少是$$$1$$$。如果 Chell 选择段 $$$[2, 2]$$$,即给出答案 TFTTT,她会犯 $$$1$$$ 错误。

在第四个测试用例中,$$$s =$$$ TNNFTF,GLaDOS 将如下安排蛋糕: TFTTF。 Chell 将选择段 $$$[2, 4]$$$ (答案: TFFFTT),产生 $$$2$$$ 错误。