题目描述

坤坤 给了强哥 $Q$ 个新的字符串（ $1 ≤ Q ≤ 100$ ），仅包含字符 M 和 O 。使用这两种字符可以得到坤坤最喜欢的单词 MOO ，因此强哥想通过以下操作让 $Q$ 个字符串都变成 MOO ：

1. 使用相反的字符替换掉字符串中的第一个或最后一个字符（因此 M 变成 O 且 O 变成 M）。
2. 删除字符串中的第一个或最后一个字符。

不幸的是，强哥 非常懒且不想进行更多不必要的操作。对于每个字符串，请帮助他计算出让这个字符串变成 MOO 所需的最少操作次数，如果无法实现则输出 -1 。

输入格式

输入的第一行包含整数 $Q$ 。

接下来 $Q$ 行每行包含一个字符串，其中每个字符都是 M 或 O。每个字符串至少有 $1$ 个字符，最多有 $100$ 个字符。

输出格式

对于每个字符串在单独的一行中输出答案。

3
MOMMOM
MMO
MOO

4
-1
0

提示

将第一个字符串变成 MOO 需要的 $4$ 次操作如下：

1. 将最后一个字符替换成 O （操作 $1$ ）
2. 删除第一个字符（操作 $2$ ）
3. 删除第一个字符（操作 $2$ ）
4. 删除第一个字符（操作 $2$ ）

第二个字符串无法变成 MOO 。第三个字符串已经是 MOO ，所以不需要进行任何操作。

测试点 $2 - 4$ 满足每个字符串长度至多为 $3$ 。

测试点 $5 - 11$ 没有额外限制。