Read problems statements in mandarin chinese, russian and vietnamese as well. 

Ada has an array of N  crayons, some crayons are pointing upwards and some downwards.
Ada thinks that an array of crayons is beautiful if all the crayons are pointing in the same direction.

In one step you can flip any segment of consecutive crayons. After flipping a segment, all crayons pointing downwards will point upwards and visceversa

What is the minimum number of steps to make the array of crayons beautiful?

------ Input ------ 

The first line of the input contains T the number of test cases.
Each test case is described in one line containing a string S of N characters, the i-th character is 'U' if the i-th crayon is pointing upwards and 'D' if it is pointing downwards.

------ Output ------ 

For each test case, output a single line containing the minimum number of flips needed to make all crayons point to the same direction.

------ Constraints ------ 

$1 ≤ T ≤ 3000$
$1 ≤ N ≤ 50$

----- Sample Input 1 ------ 
1
UUDDDUUU
----- Sample Output 1 ------ 
1
----- explanation 1 ------ 
Example case 1. In one step we can flip all the crayons pointing downwards

Source: codechef | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
for _ in range(int(input())):
	s = input()
	u = []
	d = []
	nu = 0
	nd = 0
	for c in range(len(s)):
		if s[c] == 'U':
			nu += 1
			if nd > 0:
				d.append(nd)
				nd = 0
		else:
			nd += 1
			if nu > 0:
				u.append(nu)
				nu = 0
	else:
		if nu > 0:
			u.append(nu)
		elif nd > 0:
			d.append(nd)
		print(min(len(u), len(d)))


for i in range(int(input())):
	strs = input()
	prev = 0
	d = []
	u = []
	for i in strs:
		if i == 'U' and i != prev:
			u.append(i)
			prev = i
		if i == 'D' and i != prev:
			d.append(i)
			prev = i
	print(min(len(d), len(u)))


s = int(input())
for i in range(s):
	a = input()
	b = list(a)
	count_d = 0
	count_u = 0
	for j in range(len(a) - 1):
		if b[j] != b[j + 1]:
			if b[j] == 'U':
				count_u += 1
			else:
				count_d += 1
	if b[len(a) - 1] == 'U':
		count_u += 1
	else:
		count_d += 1
	print(min(count_d, count_u))


t = int(input())
for i in range(t):
	s = input()
	d = 0
	u = 0
	for j in range(len(s) - 1):
		if s[j] != s[j + 1]:
			if s[j] == 'U':
				u = u + 1
			else:
				d = d + 1
	if s[len(s) - 1] == 'U':
		u = u + 1
	else:
		d = d + 1
	print(min(u, d))


for i in range(int(input())):
	s = input()
	s1 = '' + s[0]
	for i in s:
		if s1[-1] != i:
			s1 += i
	print(min(s1.count('U'), s1.count('D')))


for j in range(int(input())):
	s = input()
	up = 0
	dw = 0
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			if s[i - 1] == 'U':
				up += 1
			else:
				dw += 1
	if s[-1] == 'U':
		up += 1
	else:
		dw += 1
	print(min(up, dw))


for _ in range(int(input())):
	l = input()
	print(min(len(list(filter(lambda x: x != '', map(str, l.split('D'))))), len(list(filter(lambda x: x != '', map(str, l.split('U')))))))


for _ in range(int(input())):
	a = input()
	print(min(len([i for i in list(map(str, a.split('D'))) if i != '']), len([j for j in list(map(str, a.split('U'))) if j != ''])))


for _ in range(int(input())):
	a = input()
	x = list(map(str, a.split('D')))
	y = list(map(str, a.split('U')))
	m = [i for i in x if i != '']
	n = [j for j in y if j != '']
	print(min(len(m), len(n)))


from collections import Counter
t = int(input())
for _ in range(t):
	s = input()
	cnt = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			cnt += 1
	print((cnt + 1) // 2)


for _ in range(int(input())):
	s = input()
	u = 0
	d = 0
	for i in range(len(s) - 1):
		if s[i] == 'U' and s[i + 1] == 'D':
			u = u + 1
		elif s[i] == 'D' and s[i + 1] == 'U':
			d = d + 1
		else:
			continue
	if s[-1] == 'U':
		u = u + 1
	else:
		d = d + 1
	print(min(u, d))


for i in range(int(input())):
	s = input()
	a = s[0]
	j = 1
	n = len(s)
	b = {'U': 0, 'D': 0}
	while j < n:
		if s[j] == a:
			j += 1
		else:
			b[a] += 1
			a = s[j]
	b[a] += 1
	print(min(b['D'], b['U']))


t = int(input())
for i in range(t):
	s = input()
	c = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			c += 1
	print((c + 1) // 2)


for i in range(int(input())):
	s = str(input())
	(a, b) = (0, 0)
	l = []
	m = []
	for i in range(len(s)):
		if s[i] == 'U':
			a += 1
			if i < len(s) - 1:
				if s[i + 1] == 'D':
					l.append(a)
					a = 0
			elif i == len(s) - 1:
				l.append(a)
		elif s[i] == 'D':
			b += 1
			if i < len(s) - 1:
				if s[i + 1] == 'U':
					m.append(-b)
					b = 0
			elif i == len(s) - 1:
				m.append(-b)
	print(min(len(l), len(m)))


t = int(input())
for i in range(t):
	l = list(input())
	d = {'U': 0, 'D': 0}
	d[l[0]] += 1
	for j in range(1, len(l)):
		if l[j] != l[j - 1]:
			d[l[j]] += 1
	print(min(d.values()))


def find_count(l, c):
	i = 0
	cnt = 0
	while i < len(l):
		if l[i] == c:
			cnt += 1
			while i < len(l):
				if l[i] == c:
					i += 1
				else:
					break
		else:
			i += 1
	return cnt
t = int(input())
for _ in range(t):
	l = list(input())
	count1 = find_count(l, 'D')
	count2 = find_count(l, 'U')
	print(min(count2, count1))


for i in range(int(input())):
	N = input()
	N = N.upper()
	if 'D' not in N or 'U' not in N:
		print(0)
	else:
		print(min(len(list(filter(lambda x: x != '', N.split('D')))), len(list(filter(lambda x: x != '', N.split('U'))))))


t = int(input())
for _ in range(t):
	s = input()
	segments_U = 0
	segments_D = 0
	direction = s[0]
	for i in range(len(s)):
		if s[i] != direction:
			if s[i] == 'D':
				segments_U += 1
			else:
				segments_D += 1
			direction = s[i]
	if s[len(s) - 1] == 'D':
		segments_D += 1
	else:
		segments_U += 1
	print(min(segments_U, segments_D))


for i in range(int(input())):
	b = input()
	c = 0
	n = b.count('U')
	d = b.count('D')
	for i in range(len(b) - 1):
		if b[i] != b[i + 1]:
			c += 1
	print((c + 1) // 2)


for i in range(int(input())):
	S = input()
	x = 'U'
	y = 'D'
	S = S + ' '
	t1 = 0
	t2 = 0
	for j in range(len(S)):
		if S[j] == x and S[j + 1] != x:
			t1 += 1
		elif S[j] == y and S[j + 1] != y:
			t2 += 1
	print(min(t1, t2))


t = int(input())
for i in range(t):
	s = input()
	u = []
	d = []
	l = s.split('U')
	m = s.split('D')
	for i in l:
		if i != '':
			u.append(i)
	for j in m:
		if j != '':
			d.append(j)
	print(min(len(u), len(d)))


t = int(input())
for i in range(t):
	crayons = input()
	l_dir = '0'
	for j in range(1, len(crayons)):
		if crayons[j] != crayons[j - 1]:
			if l_dir[len(l_dir) - 1] == '0':
				l_dir = l_dir + '1'
			else:
				l_dir = l_dir + '0'
	print(min(l_dir.count('1'), l_dir.count('0')))


for t in range(int(input())):
	s = input()
	ul = s.split('U')
	dl = s.split('D')
	a1 = []
	a2 = []
	for i in ul:
		if i != '':
			a1.append(i)
	for i in dl:
		if i != '':
			a2.append(i)
	print(min(len(a1), len(a2)))


t = int(input())
for i in range(t):
	s = input()
	n = []
	o = []
	l = s.split('U')
	m = s.split('D')
	for i in l:
		if i != '':
			n.append(i)
	for j in m:
		if j != '':
			o.append(j)
	print(min(len(n), len(o)))


t = int(input())
for tc in range(t):
	s = input()
	c = 0
	for j in range(len(s) - 1):
		if s[j] != s[j + 1]:
			c += 1
	print((c + 1) // 2)


for i in range(int(input())):
	n = input()
	c = 0
	for j in range(len(n) - 1):
		if n[j] != n[j + 1]:
			c += 1
	print((c + 1) // 2)


import math
for _ in range(int(input())):
	s = input()
	j = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			j += 1
	print(math.ceil(j / 2))


try:
	for _ in range(int(input())):
		C = list(input())
		i = 1
		while i < len(C):
			if C[i] == C[i - 1]:
				del C[i]
			else:
				i += 1
		print(min(C.count('U'), C.count('D')))
except:
	pass


for _ in range(int(input())):
	strinput = input()
	count = 0
	for i in range(len(strinput) - 1):
		if strinput[i] != strinput[i + 1]:
			count += 1
	print((count + 1) // 2)


for t in range(int(input())):
	s = input()
	m = max(s.count('UD'), s.count('DU'))
	if m != 0 or s.count('D') == 0 or s.count('U') == 0:
		print(m)
	else:
		print(1)


t = int(input())
for i in range(t):
	s = input()
	while s.count('UU') > 0 or s.count('DD') > 0:
		s = s.replace('UU', 'U')
		s = s.replace('DD', 'D')
	print(min(s.count('U'), s.count('D')))


t = int(input())
for i in range(t):
	z = input()
	p = 0
	for i in range(len(z) - 1):
		if z[i] != z[i + 1]:
			p += 1
	if p % 2 == 0:
		print(p // 2)
	else:
		print(p // 2 + 1)
	t = t - 1


for _ in range(int(input())):
	s = input().lower()
	l = ['z']
	for i in s:
		if i != l[-1]:
			l.append(i)
	l = l[1:]
	l = min(l.count('u'), l.count('d'))
	print(l)


import math
for _ in range(int(input())):
	l = input()
	d = ''
	c = 0
	for i in l:
		if i != d:
			c += 1
			d = i
	print(c - math.ceil(c / 2))


t = int(input())
while t:
	S = input()
	c = 0
	for i in range(len(S) - 1):
		if S[i] != S[i + 1]:
			c += 1
	if c % 2 == 0:
		print(c // 2)
	else:
		print(c // 2 + 1)
	t = t - 1


t = int(input())
for i in range(t):
	count = 1
	x = str(input())
	for j in range(len(x) - 1):
		if x[j] != x[j + 1]:
			count += 1
	print(count // 2)


import re
for i in range(int(input())):
	s = input()
	(c1, c2) = (0, 0)
	ans1 = re.finditer('U+', s)
	ans2 = re.finditer('D+', s)
	for x in ans1:
		c1 += 1
	for x in ans2:
		c2 += 1
	res = min(c1, c2)
	print(res)


for _ in range(int(input())):
	s = input()
	c = 1
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			c += 1
	print(c // 2)


for tc in range(int(input())):
	str = input()
	if len(str) <= 1:
		print('0')
	else:
		count = 1
		l = len(str)
		for i in range(l - 1):
			if str[i] != str[i + 1]:
				count += 1
		print(count // 2)


T = int(input())
for i in range(T):
	S = input()
	c = 1
	for j in range(1, len(S)):
		if S[j - 1] != S[j]:
			c += 1
	print(c // 2)


T = int(input())
for _ in range(T):
	s = input()
	count = 1
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			count += 1
	print(count // 2)


for i in range(int(input())):
	a = list(input())
	d = []
	j = 0
	while j < len(a):
		s = a[j]
		while a[j] == s:
			if j + 1 < len(a) - 1:
				j += 1
			else:
				j += 1
				break
		d.append(s)
	print(min(d.count('D'), d.count('U')))


t = int(input())
for i in range(t):
	s = input()
	if len(set(s)) == 1:
		print('0')
	else:
		count = 1
		for i in range(len(s) - 1):
			if s[i] != s[i + 1]:
				count += 1
		print(count // 2)


for _ in range(int(input())):
	s = input()
	i = 0
	ans = ''
	while i < len(s):
		ch = s[i]
		while i < len(s) and ch == s[i]:
			i += 1
		ans = ans + ch
	print(len(ans) // 2)


for x in range(int(input())):
	crayons = input().upper()
	count = 1
	for x in range(len(crayons) - 1):
		if crayons[x] != crayons[x + 1]:
			count += 1
	print(count // 2)


for _ in range(int(input())):
	crayons = str(input())
	steps = 1
	for i in range(len(crayons) - 1):
		if crayons[i] != crayons[i + 1]:
			steps += 1
	print(steps // 2)


def function(s, n):
	t = 1
	for i in range(n):
		if s[i] != s[i + 1]:
			t += 1
	return t // 2
for t in range(int(input())):
	s = input()
	print(function(s, len(s) - 1))