문자열 놀이

실행 시간 제한	메모리 제한
2 초	1024 MB

📃 해결할 문제

서준이는 평소 'C,' 'O,'와 'W' 의 텍스트 문자열을 가지고 노는 것을 좋아합니다. 이를 본, 서아는 서준이에게 'M'과 'O'라는 문자들로만 이루어진 $Q$ 개의 새 문자열로 놀아보라고 제안했습니다. ( $1 \leq Q \leq 100$ ). 금방 놀이에 적응한 서준이는 'M'과 'O'로 이루어진 문자 중 'MOO' 라는 단어를 가장 좋아하게 되었고 아래의 규칙으로 $Q$ 개의 문자열을 'MOO'로 변환하려 합니다 :

첫 번째 문자나 마지막 문자를 그 반대 문자로 바꾼다 ('M'은 'O'로, 'O'는 'M'으로).
첫 번째 문자나 마지막 문자를 삭제한다.

하지만 서준이는 효율적인 것을 좋아하기 때문에 최소한의 작업만을 수행하려고 합니다. 주어진 각 문자열에 대해, 'MOO'로 변환하는 데 필요한 최소 수행 횟수를 구하고, 그럴 수 없다면 $-1$ 을 출력하세요.

💻 입력

입력의 첫 번째 줄에는 $Q$ 의 값이 주어집니다.

다음 $Q$ 개 줄에는 'M' 또는 'O'로만 이루어진 문자열이 각각 주어집니다. 각 문자열의 길이는 최소 1자, 최대 100자까지 가능합니다.

🖨️ 출력

각 입력 문자열에 대한 답을 각각의 줄에 출력합니다.

💻 예제 입력 1

3
MOMMOM
MMO
MOO

🖨️ 예제 출력 1

4
-1
0

💡 힌트

첫 번째 문자열을 'MOO'로 바꾸는 데 필요한 4번의 작업 과정은 다음과 같습니다:

마지막 문자를 O로 바꾼다(1번 작업)
첫 번째 문자를 삭제한다(2번 작업)
첫 번째 문자를 삭제한다(2번 작업)
첫 번째 문자를 삭제한다(2번 작업)

두 번째 문자열은 'MOO'로 바꿀 수 없습니다.
세 번째 문자열은 이미 'MOO'이므로, 작업을 수행할 필요가 없습니다.

점수:

입력 2-4 : 각 문자열의 길이는 최대 $3$ 까지 가능합니다.
입력 5-11 : 추가적인 제한 조건은 없습니다.

출처: USACO 2023 January Contest, Bronze Problem 3. Moo Operations