← 返回题目列表

Codeforces · 1509/B

B. TMT文档

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

学生会有一个共享文档文件。每天,学生会的一些成员都会在其中写下TMT(Towa Maji Tenshi的缩写)序列。

然而,有一天,成员们以某种方式同时将序列输入到文档中,造成了混乱。因此,找出该文件是否发生故障,就是堂岛胜的任务。具体来说,给他一个长度为 $$$n$$$ 的字符串,其字符都是 T 或 M,他想弄清楚是否可以将其划分为一些不相交的子序列,所有这些子序列都等于 TMT。也就是说,字符串的每个字符都应该恰好属于其中一个子序列。

如果可以通过删除几个(可能是零)个字符从 $$$b$$$ 获得 $$$a$$$,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n < 10^5$$$),即文档中输入的字符串中的字符数。保证 $$$n$$$ 能被 $$$3$$$ 整除。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串,仅包含字符 T 和 M。

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

输出

对于每个测试用例,如果所描述的分区存在,则打印包含 YES 的单行,否则打印包含 NO 的单行。

示例

输入 #1

5
3
TMT
3
MTT
6
TMTMTT
6
TMTTTT
6
TTMMTT

输出 #1

YES
NO
YES
NO
YES

注意

在第一个测试用例中,字符串本身已经是等于 TMT 的序列。

在第三个测试用例中,我们可以将字符串划分为子序列 TMTMTT。粗体和非粗体子序列都等于TMT。