题目详情
返回题库题目描述
农夫约翰给了奶牛贝西 $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 。
提示
样例解释 1
将第一个字符串转换为 `MOO`的 $4$ 个操作序列如下：
- 用O替换最后一个字符（操作1）
- 删除第一个字符（操作2）
- 删除第一个字符（操作2）
- 删除第一个字符（操作2）
可以证明，第二个字符串无法转换为 `MOO`。
第三个字符串已经是 `MOO`，因此无需执行任何操作。
对于 $100\%$ 的测试点，保证 $1 \le Q \le 100$, $ 1\le |S| \le 100$ 。