P19130 [HackerEarth] 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 informa
普及
题目描述

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
Register for IndiaHacksSAMPLE INPUT
8
UU
US
UUSS
USS
SUUS
UUUSS
SSUU
SUS

SAMPLE OUTPUT
-1
0
1
1
1
1
1
0

Register for IndiaHacks

输入格式

见题面

输出格式

见题面

样例输入
100 UUUUSUSUUUSSUSUUSUSSSUUUUUSUUUUSSSUUUUSSSSSSSSSSS SSUSUUUUSSUSUUUSSUUUSUUUUSSUSSSSUUSSSS SSUUSSUUUUUUSUSUSUSUSSSSSSSUSUUSUSUUUUSSSUSSSSUSSUSSUSSSUSUUUUUSUUUSSUUSUUS US UUSUUSUUUSSSUUSSUUUUUUSUSUUUUUUSUUSSSSSSSSSSSSS SUUUUUSUUSUSUSUSUSUUUSUSSSUUSUUSSSSSS SUSUUUSUSSSSSSSSUUUSSSSUUUUSSUSSSSUSUSUUSSSSSSSSUSSSSUUUUUUUUUUUUUUUU UUSUUUUUUSSSSSSS UUSUUUUUUUUSUSSUSSUUUSUSUSUSSUUUUUSSSUUSUSSSSSSUSUSUSSUUSSSSSUSUSSUUSSUUSUUSS UUUUSSUSSS SSUSUUUUSSUUUUUSSUUSSSUUUSUUUUSSSUSUUSSUSUUUUSUUSSUSSUUUUUSSSSSSSSSSSS SSUSUUUSUUSUUUSSUUUUUUUUSUSUSSSSSUUSUSSSSSSUUSUUSSSUUSUUUUUUSSSSSSSS USUSSSUUSUUSSUUUSUUSSUSUSUUUSUUSUSSSSUUSSSUSUSUUUSSS USSUSSU SUUSSUUSUSUUUSSUUSUUUSUUSUSSUSSSUUSUSUSUSUUUUUSUSUSUUUSUSSSSSSSUSSUSSUSSSUUSSUUSUUSSSSSSUSSUSUUUU SUSUUUUUUSSUSUSUSUUUUUUSSUSSUUUSSUUUSSSUSSUSUUUSUSUSSSSSUUSSSUSSSUUSUUSUUUSSSUSUSUSSUSSSUUSS SUUUUSUSUUSSSSUUUUSUUSUSUSUSUSSUUUSSSSUUUUSSUUUSSUSUSUSUUUUSSSSSSSSS USSUSUUSSSSUSSSUUSSSSUSSUUUSUSUSSSUSUSUUUUSUUSUSSUSUSUUSSSSUSSSSSUUUSSSUUSSSSUSSSUUUUUUUUUUUUUUU UUSUSUUUUUUSUUUSUUSSSSSSSSSUSSSUSUSSSSUUUUUUSSUUUSUUSUUSSSSS USSSSUSUSSUSUUUSSSUUUU SUSSSSSSUUUUUUUSUUUUUUUSSSUSUUUUUSUUSUUUUUSSSUSUSSSUUUSUSUUUSUSUUUUUSSSUUUSSSSUUSSSUSSSSSSSSSSSSSS SUUSSSUSUSUSUSUUUSSUSUSSSSSSSUUSUSSUSUSSUUSSUUSUSSSSUSSUUSSUSUUUUSSSUSSUSSUUSUSSSUSUUUUSUUUUSUUUUUU UUUUSUUUUSUUSSUSSSSSS SSSSUUSUSSSSUUUSSUSUSSUSUUUUU SUUSSSUSSSUSUUSSUUUSUUUSSSSUSUUUSUUSU SUUUUSSSSUUUSUSUUUUUSSSSUSUSUSUUUSUSSUSUUSSUUUSSSSUSS USUUUUSUSSSSUUUSUSUUSSSUUSUUUSUSSSS SSSUSUSSSSUUUSSUUSSSSUUUUSSUUUUUUUSUUSSUUSS SUSSUSSUUUSSSSSUUUUSSSSSUUSSSUSSUUSSUSUUUUUUU SUSSUUSSSUSUUSUUUUUUSSSUUSUSUSUUUSSSS SSUSUSSSSUUUSSSSSSSSUSUSUSUSUSSSUUSSSUSSSUUSUUSUSSUUUUUSUSUSUUSSSUSSSSSSUUSUUUUUUUUUUUUUUU UUUUUSSSSUUSSUUUSUUUUSUUSUSSUSUSSSSUSSUSUSSS UUSSUSSSUSUUSSUSSSUSSUSUSUUUUU SSSUSUSSUSSUUSUSUUSUUSUSSSSUSUUUSUSSSSSUSUUSUSSSUSSUSUUSUUUSUSUUUUUSSUUSSSSUUUU USSUSUSUSSUUSUSSSUSUSSUSUSSSSSSUUSUUUUUUUSUUUUSUUSSUSSUUSSUSSSSUSUUSSSUUSSUUSUSUUSSUSSSUUUU SUSSUSSSUSSUSUUSSSSUSUSSSUUSSUSSSSSUSSUUUUSUUUUUUSUUUUSUUUUUSUUUSUSSUSSSUSU SUSUUUUSSUSUSUSSUUUUSSUSSUSUSSSSUSUSUSSUUSUUSUSUUUSUUUSSS USUUSUUUSSSS USUUUSSSSSSSUUUUSUSSSUSUSSSUUUSSUUUUUUUUUUUSSUUUSSSSSSS USUUSSUSUSSUSUSUSSUSUSUUUSSSUSSSSSUSSSUUSUUSSUUUUSUUU USSSSSSUSUUSUSUUSUUU SUUSUUSSSSUUUSUUSUSSUUUSSSUUSUUUSUUUSUSSSUSUUUUSUUSSSUSSUUUSSSUSUSSUSSSSUSUUUSS SUUUUSUUSUSSUUUSSUSSUSSUUSUSUUUSUSUSUSSUUSUUUSUSUUSUSSSSSSSS SSSUUUUSUSUSSSUSUSUSUSSSSUUSSSSUUSSSSUSUUUSSUUSSUUSUSSUSSUUSUUUSUUUUU SSUUUUSUUSSUSSUUUUUSUUUSSUSUUSUSSUUUSUUUUUSSUUUSSSUSSSSSUSUUSUUSSSSSUUSSSSS SUUSUSSUSUUSSSSUSSSUUUUUUUUUSSSUUUUSUUSUUUSUUSSSSUUUSSSSSUUSUUUUSSUUSUSUUSSSUSSUUUUSSUSSUUSSSSUSSSSS UUSSUUUSUSUSSSUSUUSUUSS SSSSSSSUUUUUUUUUSUSSUSSUSUUUUUUUSUSSUSUSSUSUSUSSSSUUS USSSUUSSUSSUSUUSSUUSSUUSUUSSSUUUUSSUUSUSSUUSUUSUSUUUSSUSUSSS UUSUSSUUUUUSUSUUUSSSUUUSSSSSS UUSSUSSSSUUSSSSUUSSSUUUSUSUUUUUUSUUSUUSSSUSSS UUSUUSUUSSUUUSSSUSUUSUSUUUSUUSSUSSSUSUSSSUUUSUSUSUSSSUUUSSUUSUSSUUSSSSSSSSSSUSUUUUU USSSUUUUUSSSUUSUSSUSUUUUUUUUUSSSSSSUSSSUSUSS SSUSSSSUUUSUSUSUSSSSUSSUSSSUUSUUSSUSSSSUUSSSSSUSUUSSSSUSUUUUUUUUUUUUUUU USUSSUSUSSUSSUSSUSUSSSSUSSUUSSSSUSSUUUSUUSUUUSSSSUSUUSSUSUSUSSUUSUUUUUUUUU SSSUSSUUUUUUUSSSUSSSUSSSSUUUUSUUUUUUSSSUUSUSSUUSUUSSUUSUSUSUSUUUUSSUSSSUSUUUSSUSSSS USUSUUSSUSSUUUSUUUUSUSSUUUUSSUSSSUSUSUUSUSUSUUUUSSUUSUSUUSUUUUUUUSSUUSUSSSSSSSSSSSSSS SSUUUSUUUUUUUSSUSUUUUSSUUSSUUSUSSSUUUUSSSUUUUUUUUSUSSUUUUUSUSSSSSSSSSSSSSSSSS UUSSSUUSUUUSSS SSSSUSUUSSSSSUSUSSSUSSUUSUSUSUSUSSUUSSUUSUUSUUUUUUUUSSSSSUUSSSUSSSSUUUUUUUUU USUSUUUSUUSSSUSSSSSUSUUSSSSUSUUUUSUSSUU USUUSSSSSSUUSUUU SSUUUUSUSSUUSUSUSSSSSUSUUSSUUSSUSUSSUUUU USUSUUSSUSSUSUSSSSUSUSSUUSSSSSUUSSSUUSUSSSSUUSUUSSUUSUSSUSSUUUUUUUUUUU UUSUUSSUUUSUUUSUSUSUSUUSSSSSS UUSUUUSSUUSUSUUUUSSSUSSSS SUSUUUSUUUUSSSUUSSUUSSSUSUUSSUUSSUUUUSSSUSSSSUUSSSSSSSSUUUUUUU UUUSSSUSUSUUUUUUUUUUSSUSSUSSUUSUSUUSUSSUUUSSSUUSSSUSSSSSUUUUSUSSSSSS SUSSSUUUSUUUUSUUSSSUSSUUUSSUUSUSSSSSUUUUSSSUSUUSUUUUUUUUUUSUSSUSSUSUSUSSUUSUSUUSSUUUSSSUSSSSSSS SSUUSUSSSSUSUSUUUSSSSSUUUUSSUSUUSSUSUUSUUU UUUUUSSUSSUSSSUUSUSSSSSSUSUSSSSUSUSUUSSUUUUUUUSSSUSUUUUSUUSSUUUUSSSSSSUUUUSUSUUSSUUUSUSSS SUSUSUUUUUUSSSUUSSS SUUUSUUUSUSUUSSUSUUUSSSUSSUSSUSSSUSSSUSSSSUSUUUUSSSSUSUUUUUUSUUSSUUSSUSUUUUSUSUSS USSSUUUSUSSSUUUUSUUUSSSUUUSSSSUSSUSUSUSUUSSSUUUUSUSSUUSUSSUS SSSUSUU USUSSUUSSSUSUSUUUUSUUUUSUSSSSSUSSSSUUUUUSSSUSUSU SSUUSUSSSSSSSSUSUSSSUUSUUSSSSUSUSSSSUUSUUSSUUUSSUSSSUUUUUUUUUUUUU UUUUUUUSSUSUUUSUUUSSSSSSSSSS USSUSUUUUSSSUUSUSUUUSUSUSSSUUUSSSSUSUSUSUUUSSUUUSSSSUSUSSUUUSSSSSUUSSSSUSUUSSUUSUUSUUU UUUSSUUSUUUSSUSUUUUUUSSSSSSSSS SUSUSSSSSUUSSSUSUUUSUSSSSSUUUUSUSSSSUUSUUUUUUU SUSSUUSSSSUUSSUSUSUSSSSUUUSSUUSUSUSUSSUSSUUSUSUSUUUUU UUUUSSSSSSUSUUUUUUUSSUUUSSSUUSUSUSUUSSUSSSUUSSUUSSUSSUUSUUUSSSSUUSUUSSS SSUUUUUSSUUUUUSUUSSSSSSUSUUUUUUUUSSSUUUUUSUSUUUSUSSSSSUSSSUUUUSSUSSUUUSSUUUSUSSSSSSUUUSSSSSSS UUSSSU USUSUSUSSSUSUUUSSUSUSSSUUUUSUUSUUUUUSSUSUSSSUUSUUUSUUUUSSSSSSUUUSSSSUUSSUUSUSUSUSUUUSSUSSSSSUUSUSSS SSUUUUSSSUUSSSUSSUSUUUUSSUUSSUUSSSUUSSUSUUUUUSUSUUSSSS SSSUSSUSUUSUUUUUUSSSUUUUUSUUSSUSSSUSSUSUS UUSSUUSUSSSUUUSSSSSSSSSSUSUUUUSSSSSUUUSUUSUSSUSSUUUUUUU SUSSUUSSUSUUSSUUUSSSSUSUUSSUUUUUSUSSUSSSSSUUSSSUSSUSUSUSSUUUSSUUUUUSUUSSUUUUUUSSS U SSSSSUUUSSUUUSSSUSUUSUUUSSSUSUSUUSUUUSSSSUUUUSUSSUSSSUUSUUSSSSUUSUU SSSSUUUSSUSUUUUUUSSUUUUUUUSSSSSSUSSSUUSSUSUSUSSSSSSUSUUUUUSUSSUUUUUSSUSUSUSUUSS USSUSUSSSUSUUSSSUUUSSUSUUSUSUUSUSSSSSSSSUSSUUSUSSUSUUUUUUUU UUUUUUSSSUSSUUSUSSS USUSUUUUUSSSSS USUUUSSUSSUSUUUSSUUUSUSSSUUSUSSSSUUSUUUSS SUUUUUUSSSSSSSSSUSUUSUSUUSSSUSSUUUSSSSSUSSUUSUUSSSUUUUUUU UUSSUSUSSUUSUSSUSUSSUUUSUSSUSUUSUUSSSUUSUSSSSUUSSSUUUSUSUUUUUUUSSSSSUUUSSUSSSSUSU S
样例输出
20 -1 -1 5 8 -1 -1 -1 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 17 -1 -1 16 14 -1 -1 -1 10 18 -1 4 -1 -1 17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 12 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 25 1 -1 -1 -1 -1 -1 -1 12 -1 -1 25 -1 -1 10 -1 -1 -1 -1 0 -1 -1