This weekend Suze is having a wedding. During macedonian weddings a traditional dance called “Oro” is danced. Oro is danced by N people holding hands in a circle. Oro is a good time for boys to meet girls and vice versa. Let’s call an Oro beautiful if there are no two boys next to each other and no two girls next to each other. You are given the initial configuration of the Oro. If the Oro is not beautiful you can split it at any two points (where people hold hands) and create two Oros instead of one.

You should keep doing this until there are only beautiful Oros left. The wedding’s photographer would like to take a picture of the dancers but the more Oros there are the harder it is to take a photo.

Help the photographer by creating the least number of Oros while keeping all of them beautiful. Print the least number of beautiful Oros or -1 if this goal is impossible to achieve.

Note: the Oro is circular meaning the first and last character of the input string is connected. Also, Oro cannot be formed by only one person.

Input

The first line of input contains one positive integer T (1 <= T <= 100), the number of test cases.

For each test case there will be one line S describing the Oro. S will contain only 'M' or 'F' characters. S will have less than 31 characters.

Output

For each test case, on a separate line, output one integer, the smallest number of beautiful Oros or -1 if it’s impossible.

Constraints

Time limit: 6 seconds
Memory limit: 64 megabytes

Examples

input
4
FMMFMMMFFF
MMFFFMFMMF
MMMFMMMFMMFFFMMMFFMFFFFF
MFFFFMM

output
4
3
8
-1