The Xavier’s School for Gifted Youngsters is a special institute founded and led by Professor Charles Xavier to train young mutants in controlling their powers and help foster a friendly human-mutant relationship.
Jean and Scott commanded all young mutants to assemble at the school ground in a line for the morning drill and practice session. The mutants (boys and girls) arranged themselves in a random order, but for this particular exercise, Scott wanted boys and girls to stand alternately. So he now has to replace some students in the line to get his desired order.
Help him find the minimum number of mutants to be replaced such that all boys and girls are standing alternately.
INPUT
First line of input contains a positive integer T – denoting the number of test cases.
The first and the only line of each test case contains a string S consisting of symbols ‘b’ and ‘g’ - denoting a boy and a girl respectively.
CONSTRAINTS
1 <= T <= 100
1 <= |S| <= 105
OUTPUT For each test case, print a single line containing an integer – the minimum number of replacements required to achieve the desired order.
In Test Case 1, we can replace the 2nd and 4th ‘g’ with a ‘b’ to get the order ‘gbgbg’.
In Test Case 2, replacing the 2nd , 7th and 8th mutant with a ‘g’ , ‘b’ and a ‘g’ respectively will give us the order ‘bgbgbgbg’.
