CF1509B.TMT Document

The student council has a shared document file. Every day, some members of the student council write the sequence TMT (short for Towa Maji Tenshi) in it.

However, one day, the members somehow entered the sequence into the document at the same time, creating a jumbled mess. Therefore, it is Suguru Doujima's task to figure out whether the document has malfunctioned. Specifically, he is given a string of length $n$ whose characters are all either T or M, and he wants to figure out if it is possible to partition it into some number of disjoint subsequences, all of which are equal to TMT. That is, each character of the string should belong to exactly one of the subsequences.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero) characters.

学生会共用一份文档。每天，学生会的一些成员都会在其中写入序列 TMT（“Towa Maji Tenshi”的缩写）。

然而某天，成员们不知何故同时向文档中输入了该序列，导致文档内容变得混乱不堪。因此，须由杉浦数马来判断文档是否出现了故障。具体而言，他被给定一个长度为 $n$ 的字符串，其每个字符均为 T 或 M；他需要判断：能否将该字符串划分为若干个互不相交的子序列，使得每个子序列都恰好等于 TMT。也就是说，字符串中的每个字符必须且仅属于其中一个子序列。

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

The first line contains an integer $t$ ($1 \le t \le 5000$) — the number of test cases.

The first line of each test case contains an integer $n$ ($3 \le n \lt 10^5$), the number of characters in the string entered in the document. It is guaranteed that $n$ is divisible by $3$.

The second line of each test case contains a string of length $n$ consisting of only the characters T and M.

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

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

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

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

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

For each test case, print a single line containing YES if the described partition exists, and a single line containing NO otherwise.

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

In the first test case, the string itself is already a sequence equal to TMT.

In the third test case, we may partition the string into the subsequences TMTMTT. Both the bolded and the non-bolded subsequences are equal to TMT.

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

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