Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

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 'x' if the $i$-th student is a girl or 'y' 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?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
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 ― the maximum number of pairs.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$|S| = N$
$S$ contains only characters 'x' and 'y'
the sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3

xy

xyxxy

yy
----- Sample Output 1 ------ 
1

2

0
----- explanation 1 ------ 
Example case 1: There is only one possible pair: (first student, second student).

Example case 2: One of the ways to form two pairs is: (first student, second student) and (fourth student, fifth student). 

Another way to form two pairs is: (second student, third student) and (fourth student, fifth student).

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	s = input()
	if s[0] == 'x':
		res = s.count('xy')
		s = s.replace('xy', '')
		res += s.count('yx')
	else:
		res = s.count('yx')
		s = s.replace('yx', '')
		res += s.count('xy')
	print(res)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	i = 0
	c = 0
	while i < n - 1:
		if s[i] == 'x' and s[i + 1] == 'y' or (s[i] == 'y' and s[i + 1] == 'x'):
			c += 1
			i = i + 1
		i = i + 1
	print(c)


T = int(input())
for i in range(T):
	S = str(input())
	X = []
	Y = 0
	Y += S.count('xy')
	S = S.replace('xy', '')
	Y += S.count('yx')
	print(Y)


for t in range(int(input())):
	sd = input()
	if sd[0] == 'x':
		res = sd.count('xy')
		sd = sd.replace('xy', '')
		res += sd.count('yx')
	else:
		res = sd.count('yx')
		sd = sd.replace('yx', '')
		res += sd.count('xy')
	print(res)


T = int(input())
for i in range(T):
	s = input()
	if s[0] == 'x':
		res = s.count('xy')
		s = s.replace('xy', '')
		res += s.count('yx')
	else:
		res = s.count('yx')
		s = s.replace('yx', '')
		res += s.count('xy')
	print(res)


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	paired = [False] * len(s)
	for i in range(len(s)):
		if s[i] == 'y':
			if i > 0 and s[i - 1] == 'x' and (not paired[i - 1]):
				count += 1
				paired[i - 1] = True
			elif i < len(s) - 1 and s[i + 1] == 'x' and (not paired[i + 1]):
				count += 1
				paired[i + 1] = True
	print(count)


t = int(input())
for _ in range(t):
	a = input()
	if a[0] == 'x':
		r = a.count('xy')
		a = a.replace('xy', '')
		r = r + a.count('yx')
	else:
		r = a.count('yx')
		a = a.replace('yx', '')
		r = r + a.count('xy')
	print(r)


for _ in range(int(input())):
	s = list(input())
	i = 0
	cou = 0
	while i < len(s) - 1:
		if s[i] == 'x' and s[i + 1] == 'y' or (s[i] == 'y' and s[i + 1] == 'x'):
			cou += 1
			i += 2
		else:
			i += 1
	print(cou)


for _ in range(int(input())):
	s = input()
	acc = 0
	i = 1
	while i < len(s):
		p = s[i - 1:i + 1]
		if p in ['xy', 'yx']:
			acc += 1
			i += 2
		else:
			i += 1
	print(acc)


T = int(input())
for i in range(T):
	s = str(input())
	p = i = 0
	while i < len(s) - 1:
		if abs(ord(s[i]) - ord(s[i + 1])) == 1:
			p += 1
			i += 1
		i += 1
	print(p)


for _ in range(int(input())):
	string = input()
	if string[0] == 'x':
		count = string.count('xy')
		string = string.replace('xy', '')
		count += string.count('yx')
	else:
		count = string.count('yx')
		string = string.replace('yx', '')
		count += string.count('xy')
	print(count)


for _ in range(int(input())):
	str = input()
	if str[0] == 'x':
		a = str.count('xy')
		str = str.replace('xy', '')
		a += str.count('yx')
	else:
		a = str.count('yx')
		str = str.replace('yx', '')
		a += str.count('xy')
	print(a)


for _ in range(int(input())):
	s = input()
	res = s.count('xy')
	s = s.replace('xy', '')
	res += s.count('yx')
	print(res)


v = int(input())
for me in range(v):
	s = input()
	if s[0] == 'x':
		re = s.count('xy')
		s = s.replace('xy', '')
		re += s.count('yx')
	else:
		re = s.count('yx')
		s = s.replace('yx', '')
		re += s.count('xy')
	print(re)


for _ in range(int(input())):
	S = input()
	if S[0] == 'x':
		N = S.count('xy')
		S = S.replace('xy', '')
		N += S.count('yx')
	else:
		N = S.count('yx')
		S = S.replace('yx', '')
		N += S.count('xy')
	print(N)


for i in range(int(input())):
	string1 = input()
	if string1[0] == 'x':
		solution = string1.count('xy')
		string1 = string1.replace('xy', '')
		solution += string1.count('yx')
	else:
		solution = string1.count('yx')
		string1 = string1.replace('yx', '')
		solution += string1.count('xy')
	print(solution)


for _ in range(int(input())):
	su = input()
	if su[0] == 'x':
		resi = su.count('xy')
		su = su.replace('xy', '')
		resi += su.count('yx')
	else:
		resi = su.count('yx')
		su = su.replace('yx', '')
		resi += su.count('xy')
	print(resi)


t = int(input())
for i in range(t):
	s = input()
	if s[0] == 'x':
		h = s.count('xy')
		s = s.replace('xy', '')
		h += s.count('yx')
	else:
		h = s.count('yx')
		s = s.replace('yx', '')
		h += s.count('xy')
	print(h)


for j in range(int(input())):
	r = input()
	if r[0] == 'x':
		re = r.count('xy')
		r = r.replace('xy', '')
		re += r.count('yx')
	else:
		re = r.count('yx')
		r = r.replace('yx', '')
		re += r.count('xy')
	print(re)


for _ in range(int(input())):
	s = list(input())
	if len(set(s)) == 1:
		print(0)
	else:
		n = len(s)
		temp = '$'
		v = 0
		for i in range(n - 1):
			if s[i] != s[i + 1] and temp != i:
				temp = i + 1
				v += 1
		print(v)


for _ in range(int(input())):
	s = input()
	s += 'x' if s[-1] == 'x' else 'y'
	l = []
	i = 0
	while i < len(s) - 2:
		if s[i] != s[i + 1]:
			l.append(s[i] + s[i + 1])
			i += 2
		else:
			i += 1
	print(len(l))


for _ in range(0, int(input())):
	s = input()
	ans = 0
	if len(s) >= 2:
		i = 0
		while i + 1 < len(s):
			if s[i] != s[i + 1]:
				ans += 1
				i += 2
			else:
				i += 1
	print(ans)