Chef had a hard day and want to play little bit. The game is called "Chain". Chef has the sequence of symbols. Each symbol is either '-' or '+'. The sequence is called Chain if each two neighboring symbols of sequence are either '-+' or '+-'. 
 For example sequence '-+-+-+' is a Chain but sequence '-+-+--+' is not. 
 Help Chef to calculate the minimum number of symbols he need to replace (ex. '-' to '+' or '+' to '-') to receive a Chain sequence. 

Input

First line contains single integer T denoting the number of test cases. 
Line of each test case contains the string S consisting of symbols '-' and '+'. 


Output

For each test case, in a single line print single interger - the minimal number of symbols Chef needs to replace to receive a Chain. 


Constraints

1 ≤ T ≤ 7
1 ≤ |S| ≤ 10^5


Example
Input:
2
---+-+-+++
-------
Output:
2
3

Explanation
Example case 1.
We can change symbol 2 from '-' to '+' and symbol 9 from '+' to '-' and receive '-+-+-+-+-+'. 
Example case 2.
We can change symbols 2, 4 and 6 from '-' to '+' and receive '-+-+-+-'.
testCases = int(raw_input())
for testCase in range(testCases):
	originalString = raw_input()
	lenOfOriginalString = len(originalString)
	# count variables to find the difference between the new string and original one
	count1 = 0 # for "-+-+-+...."
	count2 = 0 # for "+-+-+-...."
	for pos in range(lenOfOriginalString):
		if (pos%2==0):
			# checking >> if char at pos = 0, 2, 4.. is "+" then count1 increased and vice-a-versa
			if (originalString[pos] == "+"):
				count1 += 1
			else: #(originalString[pos] == "-")
				count2 += 1
		else:
			# checking >> if char at pos = 1, 3, 5.. is "-" then count1 increased and vice-a-versa
			if (originalString[pos] == "-"):
				count1 += 1
			else: #(originalString[pos] == "+")
				count2 += 1
	# print the minimum 
	print min(count1,count2)