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**

**Morae Q!**

- Conversion of days into year, weeks and days.
- Find if the number is a perfect number or not.
- Compute conversion of Binary to Octal.
- Return the sum of digits in a number.
- Find if a word exists or not in a sentence.
- Convert Numbers into Words.
- Read a word if it consists only of the letters known.
- Check if the string is a dynamic string or not.
- Convert all Uppercase letters to Lowercase and vice-versa.
- Change the string such that there are no matching adjacent characters.
- Find the number of sub-strings which start and end both in 1.
- Find the start and end index of unsorted sub-array.
- Find the maximum number of pairs that can be formed.
- Figure out the number of bubbly words present.
- Check if a string is lapindrome or not even with a middle character.
- Seating layout in a triangular shaped class according to the number of rows.
- Find and Sort a sub-array which makes whole array sorted.
- Seating layout according to the number of rows.
- Find the final states of the bulbs.
- Check if reversing sub array makes the array sorted.