题目描述

学生会有一个共享文档文件。每天，学生会的一些成员会在里面写下序列 TMT（Towa Maji Tenshi 的缩写）。

然而，有一天，成员们不知怎么地同时将该序列输入到了文档中，导致文档变得一团糟。因此，现在轮到堂岛杉鲁来判断文档是否出现了故障。具体来说，他得到了一个长度为 $n$ 的字符串，其所有字符均为 T 或 M。他想要判断，是否可以将该字符串划分为若干个不相交的子序列，每个子序列都等于 TMT。也就是说，字符串中的每个字符都恰好属于一个这样的子序列。

如果字符串 $a$ 可以通过从字符串 $b$ 中删除若干（可能为零）字符得到，则称 $a$ 是 $b$ 的一个子序列。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \le n < 10^5$），表示输入字符串的长度。保证 $n$ 能被 $3$ 整除。

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

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

输出格式

对于每个测试用例，输出一行。如果存在所描述的划分方式，则输出 YES，否则输出 NO。

说明/提示

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

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

由 ChatGPT 4.1 翻译

样例

5
3
TMT
3
MTT
6
TMTMTT
6
TMTTTT
6
TTMMTT

YES
NO
YES
NO
YES