Do Bessie chán chường với chuỗi văn bản thông thường chỉ có các ký tự 'C', 'O', và 'W', Nông dân John đã cho cô \(Q\) chuỗi mới (\(1 \leq Q \leq 100\)), trong đó các ký tự chỉ có thể là 'M' và 'O'. Từ yêu thích của Bessie với các ký tự 'M' và 'O' là "MOO", vì vậy cô muốn biến đổi từng chuỗi trong số \(Q\) chuỗi thành "MOO" bằng các thao tác sau:

1. Thay thế ký tự đầu tiên hoặc ký tự cuối cùng bằng ký tự ngược lại của nó (ví dụ 'M' thành 'O' và 'O' thành 'M').
2. Xóa ký tự đầu tiên hoặc ký tự cuối cùng.

Rất tiếc, Bessie rất lười biếng và không muốn thực hiện nhiều thao tác hơn là cần thiết. Vì vậy, với mỗi chuỗi, hãy giúp cô xác định số lượng thao tác tối thiểu cần thiết để biến đổi thành "MOO" hoặc xuất \(-1\) nếu điều này là không thể.

Input

• Dòng đầu tiên chứa giá trị \(Q\).
• \(Q\) dòng tiếp theo của đầu vào mỗi dòng gồm một chuỗi, mỗi ký tự trong đó là 'M' hoặc 'O'. Mỗi chuỗi có từ 1 đến 100 ký tự.

Output

• In ra kết quả cho mỗi chuỗi đầu vào trên một dòng riêng biệt.

Scoring

• Subtask 1: Mỗi chuỗi có độ dài tối đa là \(3\).
• Subtask 2: Không có ràng buộc gì thêm.

Example

3
MOMMOM
MMO
MOO

4
-1
0