You are given a binary string S. you'll be able to perform the subsequent operations on S:
Flip: decide associate index i (1≤i≤|S|) and flip the i-th character (i.e amendment one to zero or zero to 1). For e.g. 011–001→010–001
Compress: decide any non-empty substring consisting of identical character and replace it with one prevalence of that character. For e.g. 1001111–––––10→1001–10
You want to create all the characters of the binary string equal (i.e. either all characters square measure zero or all characters square measure 1). notice the minimum variety of operations needed to try to to therefore.
Input Format
The first line of input contains one whole number T, denoting the quantity of take a look at cases. the outline of T take a look at cases follows.
The first and solely line of every action at law contains a binary string S.
Output Format
For each action at law, output one line containing one {integer|whole variety|number} - the minimum number of operations needed to create all the characters of S equal.
Constraints
1≤T≤105
1≤|S|≤106
S could be a binary string.
It is secured that the total of |S| over all take a look at cases doesn't exceed 106.
Subtasks
Subtask #1 (5 points):
1≤T≤103
1≤|S|≤10
Subtask #2 (20 points):
1≤T≤103
1≤|S|≤50
Subtask #3 (75 points):
Original constraints
Sample Input one
3
100011
1110011
000101110
Sample Output one
2
2
3
Explanation
In the 1st action at law,
1000––––11−→−−−−compress10–11
10–11−→−flip11–11
In the second action at law,
1110–011−→−flip1111–011
11110–11−→−flip11111–11
In the third action at law,
00010–1110−→−flip00011–1110
00011111––––––0−→−−−−compress0001–0
0001–0−→−flip0000–0
Code: click
ConversionConversion EmoticonEmoticon