Busy Beaver 有一天在课堂上感到无聊，决定写下一些字符串。他将一个字符串称为“重复的”（repetitive），如果它是字符 $\texttt{M}$ 后接一个或多个 $\texttt{IT}$ 的重复。例如，最短的重复字符串是 $\texttt{MIT}$，$\texttt{MITIT}$，$\texttt{MITITIT}$，……

给定一个字符串 $S$，请判断它是否可以表示为一个或多个重复字符串的拼接。

输入格式

第一行包含一个整数 $T$ ($1 \leq T \leq 1000$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $|S|$ ($3 \leq |S| \leq 2 \cdot 10^5$)，表示 $S$ 的长度。

每个测试用例的第二行包含由大写拉丁字母组成的字符串 $S$。

所有测试用例中 $|S|$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行字符串 “YES” 或 “NO”（不含引号），表示字符串 $S$ 是否为重复字符串的拼接。

你可以以任何大小写形式输出 YES 和 NO（例如，字符串 yES、yes 和 Yes 都会被识别为肯定回答）。

样例

输入 1

6
5
MITIT
4
MITI
15
MITITMITMITITIT
6
MITITM
9
MITBEAVER
5
MIIIT

输出 1

YES
NO
YES
NO
NO
NO

说明

在第一个测试用例中，整个字符串 $\texttt{MITIT}$ 是重复的。

在第二个测试用例中，可以证明该字符串不是重复字符串的拼接。

在第三个测试用例中，该字符串是以下重复字符串的拼接：$\texttt{MITIT} + \texttt{MIT} + \texttt{MITITIT}$。