There are N students standing in a row and numbered 1 through N from left to right. You are given a string S with length N, where for each valid i, the i-th character of S is ‘g’ if the i-th student is a girl or ‘b’ if this student is a boy.

Students standing next to each other in the row are friends. The students are asked to form pairs for a dance competition.

Each pair must consist of a boy and a girl. Two students can only form a pair if they are friends.

Each student can only be part of at most one pair. What is the maximum number of pairs that can be formed?

**S contains only characters 'g' and 'b'
**
**Input:**
Input contains a single integer T denoting the number of test cases.
The first and only line of each test case contains a single string S.
**Output:**
For each test case, print a single line containing one integer that represents the maximum number of pairs.

#include <stdio.h> #include <string.h> int main() { char students[100001]; int t,i; int pair; scanf("%d",&t); while(t>0){ pair=0; scanf("%s",students); for(i=0;i<strlen(students);i++){ if(students[i]=='g'&&students[i+1]=='b') {pair++; i++;} else if(students[i]=='b'&&students[i+1]=='g') {pair++; i++;}} t--; printf("%d\n",pair); } return 0; }

**INPUT_1:**

5

gbbgggbb

bgbbgb

gbbggb

bbggbbg

gbgbgbb

**OUTPUT:**

3

2

3

3

3

**INPUT_2:**

7

ggbggbg

gggbggg

bbbgbgb

gbbbbgg

bbggbgb

gbbggbg

bbbgbgg

**OUTPUT:**

2

1

2

2

3

3

2

**ILLUSTRATION**