题目描述

因为Bessie厌倦了使用她常用的字符，其中只有“C”、“O”和“W”两个字符，Farmer John给了她Q个新字符串（1≤Q≤100），其中只有M和O两个字符。Bessie最喜欢的单词“M”和“O”中的“MOO”，因此她想通过以下操作将每Q个字符串转换为“MOO“：

1.将第一个或最后一个字符替换为其相反的字符（这样“M”变为“O”，“O”变为”M“）。

2.删除第一个或最后一个字符。

不幸的是，贝西很懒，不想执行比必要更多的操作。对于每个字符串，请帮助她确定形成“MOO”所需的最小操作数或输出-1（如果不可能）。

输入格式

输入的第一行包含Q的值。接下来的Q行都由一个字符串组成，每个字符串的字符要么是“M”，要么是“O”。每个字符串至少有11个字符，最多100100个字符。

输出格式

输出每个输入字符串的答案。

3
MOMMOM
MMO
MOO

4
-1
0

提示

将第一个字符串转换为“MOO”的4个操作序列如下：

将最后一个字符替换为O（操作1）

删除第一个字符（操作2）

删除第一字符（操作3）

删除第一位字符（操作4）

第二个字符串不能转换为“MOO”。第三个字符串已经是“MOO“，因此不需要执行任何操作。

数据范围

测试点2～4：每个字符串的长度最多为33。

测试点5-11：无附加约束。