题目描述

给定一个字符串，其中的每个字符要么是 M，要么是 O。

你可以通过以下操作将该字符串变为 MOO：

1. 改变字符串中的第一个或最后一个字符（M 变为 O，O 变为 M）。
2. 删除字符串中的第一个或最后一个字符。

请你计算，为了将给定字符串变成 MOO，所需要的最少操作次数。

输入格式

第一行包含整数 $Q$，表示共有 $Q$ 组测试数据。

每组数据占一行，包含一个字符串，其中的每个字符要么是 M，要么是 O。

输出格式

每组数据输出一行结果，一个整数，表示所需要的最少操作次数。如果无解，则输出 -1。

输入样例：

3
MOMMOM
MMO
MOO

输出样例：

4
-1
0

提示

$1≤Q≤100,$ 每个字符串的长度范围 $[1,100]。$

样例解释

第一个字符串 MOMMOM 变为 MOO 最少需要 4 步操作，一种可行方案为：

1. 将最后一个字符变为 O。
2. 删除第一个字符。
3. 删除第一个字符。
4. 删除第一个字符。

第二个字符串无法变为 MOO。

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