Busy Beaver is bored in class one day and decides to write several strings. He calls a string \textit{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

Explanation

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}$.