| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 13 | 13 | 12 | 100.000% |
Busy Beaver is studying Archaeology and Materials at MIT! He has been studying ancient inscriptions made only of the letters M, I, and T and notices the following rule: any time the substring MIT appears, it may be rearranged into TIM, and any time TIM appears, it may be rearranged back into MIT.
Now Busy Beaver wants to form as many occurrences as possible of his favorite pattern, MITIT, in the string. Help him determine the maximum number of contiguous substrings equal to MITIT that can appear after performing any number of operations (possibly zero).
The first line contains an integer $T$ $(1 \le T \le 10^5)$ --- the number of test cases.
The only line of each test case contains a string of length at most 10ドル^5$ consisting of the characters M, I, and T.
The total length of all strings does not exceed 10ドル^5$.
For each test case, output a single integer --- the maximum number of substrings MITIT that can appear after performing any number of operations.
6 TITIMMIT TITITIMITIMTMTMTMMITMI MIMTITMTIMTITMTITITMTI ITMTTMITMITMTMTITITMIM MMITMITTTIMTITITTTITIT MITITIMIMIMITITITITIMIMIMIMIMIMITITITITTIIMITMTIMTIITMITMTIMTITIITITMTIMI
1 2 0 0 0 5
In the first test case, we can do the following operations: TITIMMIT $\to$ TIMITMIT and TIMITMIT $\to$ MITITMIT. We can prove that it is impossible to construct two copies of MITIT inside this string.