Moo Operations

Interview

Time limit2sMemory limit1024 MB

Summary

Given strings of M and O, find the fewest end-flips and end-deletions that turn each one into MOO, or -1 if impossible.

Level: Easy3 of 10
Topics: String, Brute force
Solved: No attempts yet

Problem

Bessie is bored of her usual text string, which only has the characters 'C', 'O', and 'W'. Farmer John gave her $Q$ new strings ( $1 \leq Q \leq 100$ ), each made only of 'M' and 'O'. Bessie's favorite word is "MOO", so she wants to turn each string into "MOO" with these operations:

Replace the first or last character with its opposite ('M' becomes 'O' and 'O' becomes 'M').
Delete the first or last character.

Bessie is lazy and does not want to perform more operations than necessary. For each string, find the minimum number of operations needed to form "MOO", or output $-1$ if it is impossible.

Input

The first line contains $Q$ . Each of the next $Q$ lines contains one string of 'M' and 'O' characters. Each string has at least 1 and at most 100 characters.

Output

For each string, print the answer on its own line.

Hint

The sequence of 4 operations that turns the first string into "MOO" is:

Replace the last character with O (operation 1)
Delete the first character (operation 2)
Delete the first character (operation 2)
Delete the first character (operation 2)

The second string cannot be turned into "MOO". The third string is already "MOO", so no operations are needed.

Examples1

Example 1
Input
```
3
MOMMOM
MMO
MOO
```
Expected output
```
4
-1
0
```