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 想让 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 可以保证的最大错误数。
示例
输入复制
104FTFF5TNFTT6TFTTTN6TNNFTF7TNFNTNF6NNFFNN7TNTFNTN1N5NNNNN10NNNTTNNNFN
输出复制
1012222023
注意
在第一个测试用例中,$$$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$$$ 错误。