Transform to MOO

Bessie is given $Q$ new strings, each consisting only of the characters M and O. Her goal is to convert each string into the word MOO using the following operations:

1. Replace either the first or last character with its opposite (i.e. change M to O or O to M).
2. Delete either the first or last character.

Determine the minimum number of operations needed to obtain exactly MOO from the given string, or output $-1$ if it is impossible.

Note: Operations can only be applied to the first or last character of the current string. In the final string MOO (which has length 3), the middle character is never on the boundary, so it must originally be O when the string reaches length 3.

inputFormat

The first line contains an integer $Q$ ($1\le Q\le 100$), representing the number of strings. Each of the following $Q$ lines contains a string consisting solely of the characters M and O.

outputFormat

For each input string, output a single integer on a new line — the minimum number of operations required to transform the string into MOO, or $-1$ if it is impossible.

sample

1
MOO

0