Grey Worm has learnt that Daario Naharis's Second Sons have combined with his Unsullied to improve Daenerys's strength. The combined army is standing in a big line. You are given information of their arrangement by a string s. The string s consists of only letters 'U' and 'S', where 'U' represents an Unsullied and 'S' represents a Second Son.

Grey Worm wants inter-troop interaction among his army to be maximum. So he does not like seeing two or more Unsullied/Second Sons standing nearby (i.e. continuous) in the line. e.g. he does not like the arrangements UUS and USS, but he likes US, SUS etc. Now by seeing the initial arrangement s of the combined army, Grey Worm may get furious and now he wants to change this arrangement into a likable arrangement. For achieving that, he can swap positions of any two Troops (not necessary continuous). Let the cost of swapping people from position i with position j (i ≠ j) be 1.

Please help Grey Worm in finding minimum cost of swaps needed to convert the current arrangement into a likable one.

Input

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow. Then the next line contains string s of length n, denoting the initial arrangement s of Army. Note that the integer n is not given explicitly in input.

Output

For each test case, print a single line containing the answer of the test case, that is, the minimum cost to convert the current arrangement into a likable one. If it is not possible to convert the current arrangement into a likable one, then print -1 instead of the minimum cost.

Constraints

1 ≤ T ≤ 10^3

1 ≤ n ≤ 10^4