| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 256 MB | 64 | 43 | 41 | 66.129% |
Busy Beaver is bored in class one day and decides to write several strings. He calls a string repetitive if it is the character M suffixed with one or more repetitions of IT. For example, the shortest repetitive strings are MIT, MITIT, MITITIT, $\dots$.
You are given a string $S$. Determine whether it can be expressed as the concatenation of one or more repetitive strings.
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$.
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.
6 5 MITIT 4 MITI 15 MITITMITMITITIT 6 MITITM 9 MITBEAVER 5 MIIIT
YES NO YES NO NO NO
In the first test case, the entire string 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: MITIT + MIT + MITITIT.
University > MIT > M(IT)^2 > M(IT)^2 Winter 2025 Tournament > Beginner Round 2번