本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

由于贝茜玩腻了她平常只包含字符 'C'、'O'、'W' 的文本串，农夫约翰给了她 $Q$ 个新字符串（$1 \leq Q \leq 100$），这些字符串只包含 'M' 和 'O' 两种字符。 贝茜最喜欢由 'M' 和 'O' 组成的单词显然是 "MOO"，所以她想用以下操作把每个字符串变成 "MOO"： 将第一个或最后一个字符替换为其相反字符（即 'M' 变为 'O'，'O' 变为 'M'）。 删除第一个或最后一个字符。 不幸的是，贝茜很懒，不想执行超过绝对必要数量的操作。对于每个字符串，请你帮助她确定变成 "MOO" 所需的最少操作次数；如果不可能，则输出 $-1$。

输入格式

第一行输入为 $Q$。 接下来的 $Q$ 行每行输入一个字符串，字符串中的每个字符均为 'M' 或 'O'。每个字符串长度至少为 1，至多为 100。

输出格式

对每个输入字符串，输出一行答案。

3
MOMMOM
MMO
MOO

4
-1
0

提示

将第一个字符串变为 "MOO" 的一组共 $4$ 次操作如下： 将最后一个字符替换为 O（操作 1） 删除第一个字符（操作 2） 删除第一个字符（操作 2） 删除第一个字符（操作 2） 第二个字符串无法变为 "MOO"。第三个字符串已经是 "MOO"，因此不需要进行任何操作。 SCORING: Inputs 2-4：每个字符串长度至多为 $3$。 Inputs 5-11：无额外限制。 Problem credits: Aryansh Shrivastava

来源

USACO|2023|Bronze