Busy Beaver 正在 MIT 学习考古学和材料学！他一直在研究仅由字母 M、I 和 T 组成的古代碑文，并发现了以下规律：任何时候只要出现子串 MIT，就可以将其重新排列为 TIM；同样，任何时候只要出现子串 TIM，也可以将其重新排列回 MIT。

现在，Busy Beaver 想要在字符串中形成尽可能多的他最喜欢的模式 MITIT。请帮助他确定，在进行任意次数（可能为零次）的操作后，字符串中最多可以同时出现多少个等于 MITIT 的连续子串。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$) —— 测试用例的数量。

每个测试用例的唯一一行包含一个长度最多为 $10^5$ 的字符串，由字符 M、I 和 T 组成。

所有字符串的总长度不超过 $10^5$。

输出格式

对于每个测试用例，输出一个整数 —— 在进行任意次数的操作后，最多可以同时出现的 MITIT 子串数量。

样例

输入格式 1

6
TITIMMIT
TITITIMITIMTMTMTMMITMI
MIMTITMTIMTITMTITITMTI
ITMTTMITMITMTMTITITMIM
MMITMITTTIMTITITTTITIT
MITITIMIMIMITITITITIMIMIMIMIMIMITITITITTIIMITMTIMTIITMITMTIMTITIITITMTIMI

输出格式 1

1
2
0
0
0
5

说明

在第一个测试用例中，我们可以进行以下操作：TITIMMIT $\to$ TIMITMIT，然后 TIMITMIT $\to$ MITITMIT。可以证明，无法在此字符串中构建两个 MITIT 副本。