题目描述

农夫约翰给了奶牛贝西 $Q$ 个新字符串 $(1\le Q\le100)$ ，其中只有字符 M 和 O ，她想将 $Q$ 个字符串都变成 MOO。

贝西可以用如下的方式改变字符串：

• 用相反的字符替换第一个或最后一个字符（将 M 变成 O ，将 O 变成 M ）。
• 删除第一个或最后一个字符。

贝西只想用最少的次数完成改变。请你帮她找到需要的最小改变次数。如果不可能在有限的步数中完成这个任务，请输出 -1 。

输入格式

输入数据的第一行是一个正整数 $Q$ 。

接下来的 $Q$ 行中，每行一个只包含大写字母 M 或 O 的字符串 $S$ ，保证 $1\le |S| \le 100$ 。

输出格式

输出 $Q$ 行，每行为该测试点最小操作次数，如果不可能在有限的步数中完成这个任务，请输出 -1 。

3
MOMMOM
MMO
MOO

4
-1
0

提示

样例解释 1

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

• 用O替换最后一个字符（操作1）
• 删除第一个字符（操作2）
• 删除第一个字符（操作2）
• 删除第一个字符（操作2）

可以证明，第二个字符串无法转换为 MOO。

第三个字符串已经是 MOO，因此无需执行任何操作。

数据范围

对于 $100\%$ 的测试点，保证 $1 \le Q \le 100$, $1\le |S| \le 100$ 。