second-sons-join-unsullied-3
Source: hackerearth
Difficulty: HARD

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


noOfTestCases = int(input())

def isPossible(string):
	countOfU = 0
	countOfS = 0
	
	for s in string:
		if(s == 'S'):
			countOfS += 1
		else:
			countOfU += 1
			
	if(countOfS > countOfU + 1 or countOfU > countOfS + 1):
		return -1
	
	firstStringToCompare = ""
	secondStringToCompare = ""
	
	
	for i in range(1, len(string)+1):
		if(i%2!=0):
			firstStringToCompare += "S"
			secondStringToCompare += "U"
		else:
			firstStringToCompare += "U"
			secondStringToCompare += "S"
	
	StoUDiff1 = 0
	UtoSDiff1 = 0
	
	StoUDiff2 = 0
	UtoSDiff2 = 0
	
	start = 0
	while(start < len(string)):
		if(string[start] == 'S' and firstStringToCompare[start] == 'U'):
			StoUDiff1 += 1
		elif(string[start] == 'U' and firstStringToCompare[start] == 'S'):
			UtoSDiff1 += 1
	
		if(string[start] == 'S' and secondStringToCompare[start] == 'U'):
			StoUDiff2 += 1
		elif(string[start] == 'U' and secondStringToCompare[start] == 'S'):
			UtoSDiff2 += 1
		start += 1
		
	if(StoUDiff1 != UtoSDiff1 and StoUDiff2 != UtoSDiff2):
		return -1
	
	if(StoUDiff1 == UtoSDiff1 and StoUDiff2 != UtoSDiff2):
		return StoUDiff1
	
	if(StoUDiff2 == UtoSDiff2 and StoUDiff1 != UtoSDiff1):
		return StoUDiff2
	if(StoUDiff2 == UtoSDiff2 and StoUDiff1 == UtoSDiff1):
		return min(StoUDiff2, StoUDiff1)


	
for caseNo in range(1, noOfTestCases + 1):
	print(isPossible(input()))


t= int(input())
for _ in range(t):
	a=input().strip()
	c1=0
	c2 = 0
	for i in range(len(a)):
		if a[i]=='U':
			c1+=1
		else:
			c2+=1
	if(len(a)%2==0):
		if c1!=c2:
			print("-1")
		else:
			lis=[]
			lis1=[]
			for z in range(c1):
				lis.append('S')
				lis.append('U')
			for z in range(c1):
				lis1.append('U')
				lis1.append('S')
			#print lis,lis1
			count =0
			count1 =0 
			for z in range(len(a)):
				if lis[z]!=a[z]:
					count+=1
			for z in range(len(a)):
				if lis1[z]!=a[z]:
					count1+=1
			#print count,count1
			print(min(count/2,count1/2))
					
				
	else:
		if c1==c2+1 or c2 == c1+1:
			lis=[]
			if c1==c2+1:
				count =0
				for j in range(c2):
					lis.append('U')
					lis.append('S')
				lis.append('U')
				for j in range(len(a)):
					if lis[j]!=a[j]:
						count +=1
				print(count/2)
			else:
				count1 =0
				for j in range(c1):
					lis.append('S')
					lis.append('U')
				lis.append('S')
				for j in range(len(a)):
					if lis[j]!=a[j]:
						count1 +=1
				print(count1/2)
		else:
			print("-1")
		
			


noOfTestCases = int(input())

def isPossible(string):
	countOfU = 0
	countOfS = 0
	
	for s in string:
		if(s == 'S'):
			countOfS += 1
		else:
			countOfU += 1
			
	if(countOfS > countOfU + 1 or countOfU > countOfS + 1):
		return -1
	
	firstStringToCompare = ""
	secondStringToCompare = ""
	
	
	for i in range(1, len(string)+1):
		if(i%2!=0):
			firstStringToCompare += "S"
			secondStringToCompare += "U"
		else:
			firstStringToCompare += "U"
			secondStringToCompare += "S"
	
	StoUDiff1 = 0
	UtoSDiff1 = 0
	
	StoUDiff2 = 0
	UtoSDiff2 = 0
	
	start = 0
	
	while(start < len(string)):
		if(string[start] == 'S' and firstStringToCompare[start] == 'U'):
			StoUDiff1 += 1
		elif(string[start] == 'U' and firstStringToCompare[start] == 'S'):
			UtoSDiff1 += 1
	
		if(string[start] == 'S' and secondStringToCompare[start] == 'U'):
			StoUDiff2 += 1
		elif(string[start] == 'U' and secondStringToCompare[start] == 'S'):
			UtoSDiff2 += 1
		start += 1
		
	if(StoUDiff1 != UtoSDiff1 and StoUDiff2 != UtoSDiff2):
		return -1
	
	if(StoUDiff1 == UtoSDiff1 and StoUDiff2 != UtoSDiff2):
		return StoUDiff1
	
	if(StoUDiff2 == UtoSDiff2 and StoUDiff1 != UtoSDiff1):
		return StoUDiff2
		
	if(StoUDiff2 == UtoSDiff2 and StoUDiff1 == UtoSDiff1):
		return min(StoUDiff2, StoUDiff1)


	
for caseNo in range(1, noOfTestCases + 1):
	print(isPossible(input()))