B. M(IT)+
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is bored in class one day and decides to write several strings. He calls a string repetitive if it is the character $$$\texttt{M}$$$ suffixed with one or more repetitions of $$$\texttt{IT}$$$. For example, the shortest repetitive strings are $$$\texttt{MIT}$$$, $$$\texttt{MITIT}$$$, $$$\texttt{MITITIT}$$$, ....

You are given a string $$$S$$$. Determine whether it can be expressed as the concatenation of one or more repetitive strings.

Input

The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$|S|$$$ ($$$3 \leq |S| \leq 2 \cdot 10^5$$$) — the length of $$$S$$$.

The second line of each test case contains the string $$$S$$$ consisting of uppercase Latin characters.

The sum of $$$|S|$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single string "YES" or "NO" (without the quotes) denoting if the string $$$S$$$ is a concatenation of repetitive strings.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Example
Input
6
5
MITIT
4
MITI
15
MITITMITMITITIT
6
MITITM
9
MITBEAVER
5
MIIIT
Output
YES
NO
YES
NO
NO
NO
Note

In the first test case, the entire string $$$\tt{MITIT}$$$ is repetitive.

In the second test case, it can be shown that the string is not a concatenation of repetitive strings.

In the third test case, the string is the following concatenation of repetitive strings: $$$\texttt{MITIT} + \texttt{MIT} + \texttt{MITITIT}$$$.