Read problems statements in Mandarin Chinese  and Russian. 

Chef had a hard day and want to play little bit. The game is called "Chain". Chef has the sequence of symbols. Each symbol is either '-' or '+'. The sequence is called Chain if each two neighboring symbols of sequence are either '-+' or '+-'. 
For example sequence '-+-+-+' is a Chain but sequence '-+-+--+' is not. 
Help Chef to calculate the minimum number of symbols he need to replace (ex. '-' to '+' or '+' to '-') to receive a Chain sequence. 

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

First line contains single integer T denoting the number of test cases. 
Line of each test case contains the string S consisting of symbols '-' and '+'. 

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

For each test case, in a single line print single interger - the minimal number of symbols Chef needs to replace to receive a Chain. 

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

$1 ≤ T ≤ 7$
$1 ≤ |S| ≤ 10^{5}$

------ Subtasks ------ 

$Subtask 1 ≤ |S| ≤ 10, 1 ≤ T ≤ 7 Points: 20 $

$Subtask 1 ≤ |S| ≤ 1000, 1 ≤ T ≤ 7 Points: 30 $

$Subtask 1 ≤ |S| ≤ 10^{5}, 1 ≤ T ≤ 7Points: 50 $

----- Sample Input 1 ------ 
2
---+-+-+++
-------
----- Sample Output 1 ------ 
2
3
----- explanation 1 ------ 
Example case 1.
We can change symbol 2 from '-' to '+' and symbol 9 from '+' to '-' and receive '-+-+-+-+-+'. 
Example case 2.
We can change symbols 2, 4 and 6 from '-' to '+' and receive '-+-+-+-'.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Complete search


Solutions:
from math import gcd, sqrt, ceil, floor, log10
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache
import sys
import time
import string
sys.setrecursionlimit(3000000)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def solve(*args, **kwargs):
	s = args[0]
	res1 = res2 = 0
	for (idx, ch) in enumerate(s):
		res1 += idx & 1 and ch == '+'
		res1 += idx & 1 == 0 and ch == '-'
		res2 += idx & 1 == 0 and ch == '+'
		res2 += idx & 1 and ch == '-'
	return min(res1, res2)

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(str)
		res = solve(*(arg1,))
		if type(res) in {list, tuple, set}:
			print(*res, sep='')
		else:
			print(res)
main()


t = int(input())
for i in range(t):
	s = input()
	c = d = 0
	if s.count('+') == len(s) or s.count('-') == len(s):
		print(len(s) // 2)
	else:
		for j in range(len(s)):
			if j % 2 == 0:
				if s[j] == '-':
					d += 1
				else:
					c += 1
			elif s[j] == '+':
				d += 1
			else:
				c += 1
		print(min(c, d))


T = int(input())
for _ in range(T):
	A = [str for str in input()]
	N = len(A)
	prev = A[0]
	ans = 0
	for i in range(1, N):
		if A[i] == prev:
			ans += 1
			if A[i] == '-':
				A[i] = '+'
			else:
				A[i] = '-'
		prev = A[i]
	print(min(ans, N - ans))


from collections import Counter
for _ in range(int(input())):
	a = list(input())
	b = ['-' if i % 2 else '+' for i in range(len(a))]
	c = ['+' if i % 2 else '-' for i in range(len(a))]
	m = p = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			m += 1
	for i in range(len(a)):
		if a[i] != c[i]:
			p += 1
	print(min(m, p))


def solve(st):
	n = len(st)
	bad = 0
	for (i, it) in enumerate(st):
		if i % 2 and it == '+' or (i % 2 == 0 and it == '-'):
			bad += 1
	ans = min(bad, n - bad)
	return ans
for case in range(int(input())):
	st = input()
	ans = solve(st)
	print(ans)


t = int(input())
for r in range(t):
	s = input()
	(c1, c2) = (0, 0)
	for i in range(len(s)):
		if i % 2 == 0 and s[i] != '+':
			c1 += 1
		elif i % 2 != 0 and s[i] != '-':
			c1 += 1
		if i % 2 == 0 and s[i] == '+':
			c2 += 1
		elif i % 2 != 0 and s[i] == '-':
			c2 += 1
	print(min(c1, c2))


for _ in range(int(input())):
	a = input()
	b = a
	count = 0
	count1 = 0
	k = j = 0
	le = len(a)
	for i in range(le):
		if le % 2 != 0:
			le -= 1
			if a[-1] == '-':
				count1 += 1
			elif b[-1] == '+':
				count += 1
		if k >= le:
			break
		if a[k:k + 2] != '-+':
			if a[k:k + 2] == '+-':
				count += 2
			else:
				count += 1
		if b[k:k + 2] != '+-':
			if b[k:k + 2] == '-+':
				count1 += 2
			else:
				count1 += 1
		k += 2
	print(min(count, count1))


for _ in range(int(input())):
	d = input()
	co = 0
	x = 0
	for j in range(len(d)):
		if j % 2 == 0 and d[j] == '+':
			co += 1
		elif j % 2 != 0 and d[j] == '-':
			co += 1
		if j % 2 == 0 and d[j] == '-':
			x += 1
		elif j % 2 != 0 and d[j] == '+':
			x += 1
	print(min(co, x))


from math import ceil
t = int(input())
for ni in range(t):
	s = input()
	(cp, cm) = (0, 0)
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] == '+':
				cp = cp + 1
			else:
				cm = cm + 1
		elif s[i] == '+':
			cm = cm + 1
		else:
			cp = cp + 1
	print(min(cm, cp))


t = input()
for c in range(0, int(t)):
	s = input()
	flip = 0
	count1 = 0
	for x in range(0, len(s)):
		if flip == 0 and s[x] == '+':
			count1 = count1 + 1
		elif flip == 1 and s[x] == '-':
			count1 = count1 + 1
		if flip == 0:
			flip = 1
		else:
			flip = 0
	flip = 1
	count2 = 0
	for y in range(0, len(s)):
		if flip == 0 and s[y] == '+':
			count2 = count2 + 1
		elif flip == 1 and s[y] == '-':
			count2 = count2 + 1
		if flip == 0:
			flip = 1
		else:
			flip = 0
	print(min(count1, count2))


for _ in range(int(input())):
	ip = list(input())
	n = len(ip)
	count = 0
	for i in range(0, n - 1):
		if ip[i] == ip[i + 1]:
			if ip[i + 1] == '-':
				ip[i + 1] = '+'
			else:
				ip[i + 1] = '-'
			count += 1
	print(min(count, n - count))


t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	a = '+-' * (l // 2)
	b = '-+' * (l // 2)
	if l % 2 != 0:
		a += '+'
		b += '-'
	c1 = 0
	c2 = 0
	for j in range(l):
		if s[j] != a[j]:
			c1 += 1
		elif s[j] != b[j]:
			c2 += 1
	print(min(c1, c2))


t = int(input())
while t != 0:
	s = input()
	c = 0
	d = 0
	ans1 = []
	for i in range(len(s)):
		if i % 2 == 0:
			ans1.append('+')
		else:
			ans1.append('-')
	ans2 = []
	for i in range(len(s)):
		if i % 2 == 0:
			ans2.append('-')
		else:
			ans2.append('+')
	for i in range(len(s)):
		if s[i] != ans1[i]:
			c += 1
		if s[i] != ans2[i]:
			d += 1
	print(min(c, d))
	t -= 1


for _ in range(int(input())):
	s = input().strip()
	c = 0
	n = len(s)
	for i in range(n):
		if i % 2 == 0 and s[i] == '+':
			c += 1
		elif i % 2 == 1 and s[i] == '-':
			c += 1
	print(min(c, n - c))


for _ in range(int(input())):
	l = list(input())
	(c, d) = (0, 0)
	for i in range(0, len(l), 2):
		if l[i] == '-':
			c += 1
	for i in range(1, len(l), 2):
		if l[i] == '+':
			c += 1
	for i in range(0, len(l), 2):
		if l[i] == '+':
			d += 1
	for i in range(1, len(l), 2):
		if l[i] == '-':
			d += 1
	print(min(c, d))


for _ in range(int(input())):
	s = str(input())
	a = '-'
	b = '+'
	m = float('Inf')
	count = 0
	for i in s:
		if i != a:
			count += 1
		if a == '-':
			a = '+'
		else:
			a = '-'
	m = min(count, m)
	count = 0
	for i in s:
		if i != b:
			count += 1
		if b == '+':
			b = '-'
		else:
			b = '+'
	m = min(m, count)
	print(m)


T = int(input())
for i in range(T):
	l = list(input())
	(start_minus, start_plus) = (0, 0)
	for i in range(0, len(l), 2):
		if l[i] == '-':
			start_minus += 1
	for i in range(1, len(l), 2):
		if l[i] == '+':
			start_minus += 1
	for i in range(0, len(l), 2):
		if l[i] == '+':
			start_plus += 1
	for i in range(1, len(l), 2):
		if l[i] == '-':
			start_plus += 1
	print(min(start_minus, start_plus))


for _ in range(int(input())):
	s = input()
	n = len(s)
	(start_minus, start_plus) = (0, 0)
	for i in range(n):
		if i % 2 == 0 and s[i] != '-' or (i % 2 != 0 and s[i] == '-'):
			start_minus += 1
		if i % 2 == 0 and s[i] != '+' or (i % 2 != 0 and s[i] == '+'):
			start_plus += 1
	print(min(start_minus, start_plus))


for _ in range(int(input())):
	s = input()
	a = b = 0
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] == '+':
				a += 1
			else:
				b += 1
		elif s[i] == '-':
			a += 1
		else:
			b += 1
	print(min(a, b))


tests = int(input())
for i in range(tests):
	string = input()
	length = len(string)
	if length == 1:
		print(0)
	else:
		arr = list(string)
		ans_1 = 0
		ans_2 = 0
		for j in range(length):
			if arr[j] == '+' and j & 1 or (arr[j] == '-' and j % 2 == 0):
				ans_1 += 1
			if arr[j] == '-' and j & 1 or (arr[j] == '+' and j % 2 == 0):
				ans_2 += 1
		print(min(length - ans_1, length - ans_2))


for tc in range(int(input())):
	s = input()
	(pswitch, nswitch) = (0, 0)
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] != '-':
				nswitch += 1
			else:
				pswitch += 1
		elif s[i] != '+':
			nswitch += 1
		else:
			pswitch += 1
	print(min(pswitch, nswitch))


for _ in range(int(input())):
	a = input()
	b = a
	if a.count('--') == 0 and a.count('++') == 0:
		print(0)
	else:
		c = 0
		a = list(a)
		o = a[0]
		for i in range(1, len(a)):
			if o == a[i]:
				c = c + 1
				if o == '-':
					a[i] = '+'
				else:
					a[i] = '-'
			o = a[i]
		c1 = 1
		b = list(b)
		o = a[0]
		if o == '-':
			o = '+'
			b[0] = '+'
		else:
			o = '-'
			b[0] = '-'
		for i in range(1, len(b)):
			if o == b[i]:
				c1 = c1 + 1
				if o == '-':
					b[i] = '+'
				else:
					b[i] = '-'
			o = b[i]
		print(min(c, c1))


t = int(input(''))
if 1 <= t <= 7:
	for _ in range(t):
		st = input('')
		s = []
		s1 = []
		s2 = []
		s1s = s2s = 0
		if 1 <= len(st) <= 10 ** 5:
			for i in range(len(st)):
				s.append(st[i])
				if i % 2 == 0:
					s1.append('+')
					s2.append('-')
				else:
					s1.append('-')
					s2.append('+')
				if s[i] != s1[i]:
					s1s += 1
				if s[i] != s2[i]:
					s2s += 1
			if s1s > s2s:
				print(s2s)
			else:
				print(s1s)


t = int(input())
while t > 0:
	a = input()
	n = len(a)
	s = ''
	s = '-+' * (n // 2)
	st = '+-' * (n // 2)
	if n % 2 == 1:
		s = s + '-'
		st = st + '+'
	c1 = 0
	c2 = 0
	for i in range(0, n):
		if s[i] != a[i]:
			c1 = c1 + 1
		if st[i] != a[i]:
			c2 = c2 + 1
	print(min(c1, c2))
	t = t - 1


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	check1 = '+-' * (n // 2)
	check2 = '-+' * (n // 2)
	if n % 2 != 0:
		check1 += '+'
		check2 += '-'
	count1 = count2 = 0
	for i in range(n):
		if s[i] != check1[i]:
			count1 += 1
		elif s[i] != check2[i]:
			count2 += 1
	print(min(count1, count2))


t = int(input())
for i in range(t):
	s = input()
	c = 0
	d = 0
	for j in range(len(s)):
		if j % 2 == 0 and s[j] == '-':
			continue
		elif j % 2 != 0 and s[j] == '+':
			continue
		else:
			c = c + 1
	for j in range(len(s)):
		if j % 2 == 0 and s[j] == '+':
			continue
		elif j % 2 != 0 and s[j] == '-':
			continue
		else:
			d = d + 1
	print(min(c, d))


for _ in range(int(input())):
	s = input()
	n = len(s)
	a = '+-' * (n // 2)
	b = '-+' * (n // 2)
	if n % 2 != 0:
		a = a + '+'
		b = b + '-'
	count1 = 0
	count2 = 0
	for i in range(n):
		if s[i] != a[i]:
			count1 += 1
		elif s[i] != b[i]:
			count2 += 1
	print(min(count1, count2))


for i in range(int(input())):
	s = input()
	a = len(s)
	l = []
	count = 0
	for i in s:
		l.append(i)
	for j in range(a - 1):
		if l[j] == '-':
			if l[j + 1] == '+':
				continue
			else:
				l[j + 1] = '+'
				count = count + 1
		elif l[j + 1] == '-':
			continue
		else:
			l[j + 1] = '-'
			count = count + 1
	print(min(count, a - count))


for _ in range(int(input())):
	s = input()
	c1 = 0
	c2 = 0
	for i in range(len(s)):
		if i % 2 == 0:
			if s[i] == '-':
				c2 += 1
			else:
				c1 += 1
		elif s[i] == '+':
			c2 += 1
		else:
			c1 += 1
	if c1 >= c2:
		print(c2)
	else:
		print(c1)


for _ in range(int(input())):
	s = input()
	n = len(s)
	p1 = 0
	p2 = 0
	for i in range(n):
		if i % 2 == 0 and s[i] == '-':
			p1 += 1
		elif i % 2 == 1 and s[i] == '+':
			p1 += 1
		if i % 2 == 0 and s[i] == '+':
			p2 += 1
		elif i % 2 == 1 and s[i] == '-':
			p2 += 1
	print(min(p1, p2))


for _ in range(int(input())):
	a = input()
	c1 = 0
	c2 = 0
	d1 = 0
	d2 = 0
	for i in range(0, len(a)):
		if i % 2 == 0:
			if a[i] == '-':
				c1 += 1
			else:
				c2 += 1
		elif a[i] == '+':
			d1 += 1
		else:
			d2 += 1
	if c1 + d1 < d2 + c2:
		print(c1 + d1)
	else:
		print(d2 + c2)


t = int(input())
for _ in range(t):
	string = input()
	minus1 = 0
	plus1 = 0
	plus2 = 0
	minus2 = 0
	for i in range(0, len(string)):
		if i % 2 == 0:
			if string[i] == '-':
				minus1 += 1
			else:
				plus1 += 1
		elif string[i] == '+':
			plus2 += 1
		else:
			minus2 += 1
	if minus1 + plus2 < minus2 + plus1:
		print(minus1 + plus2)
	else:
		print(minus2 + plus1)


ttt = int(input())
for _ in range(ttt):
	seq = input()
	(s1, s2) = ('', '')
	for i in range(len(seq)):
		if i % 2 == 0:
			s1 += '+'
			s2 += '-'
		else:
			s1 += '-'
			s2 += '+'
	(c1, c2) = (0, 0)
	for i in range(len(seq)):
		if seq[i] != s1[i]:
			c1 += 1
		if seq[i] != s2[i]:
			c2 += 1
	print(min(c1, c2))


a = int(input())
for i in range(a):
	b = list(input())
	(c, d) = (0, 0)
	for j in range(0, len(b), 2):
		if b[j] == '+':
			c = c + 1
	for j in range(1, len(b), 2):
		if b[j] == '-':
			c = c + 1
	for j in range(0, len(b), 2):
		if b[j] == '-':
			d = d + 1
	for j in range(1, len(b), 2):
		if b[j] == '+':
			d = d + 1
	print(min(c, d))


t = int(input())
while t > 0:
	t -= 1
	s = input('')
	n = len(s)
	splus = ''
	sminus = ''
	for i in range(n):
		if i % 2 == 0:
			splus += '+'
			sminus += '-'
		else:
			splus += '-'
			sminus += '+'
	x = 0
	y = 0
	for i in range(n):
		if s[i] != splus[i]:
			x += 1
		if s[i] != sminus[i]:
			y += 1
	print(min(x, y))


T = int(input())
ans = []
for _ in range(T):
	S = list(input())
	N = len(S)
	start_plus = 0
	start_minus = 0
	for i in range(N):
		if i % 2 == 0 and S[i] == '+' or (i % 2 == 1 and S[i] == '-'):
			start_plus += 1
		if i % 2 == 0 and S[i] == '-' or (i % 2 == 1 and S[i] == '+'):
			start_minus += 1
	x = max(start_plus, start_minus)
	ans.append(N - x)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	s = list(input())
	cnt = 0
	s1 = s[:]
	for i in range(0, len(s) - 1):
		if s[i] == s[i + 1]:
			if s[i + 1] == '-':
				s[i + 1] = '+'
			else:
				s[i + 1] = '-'
	for (i, j) in zip(s, s1):
		if i != j:
			cnt += 1
	print(min(cnt, len(s) - cnt))


for _ in range(int(input())):
	s = input()
	n = len(s)
	x1 = 0
	x2 = 0
	s1 = '-+' * (n // 2)
	s2 = '+-' * (n // 2)
	if n % 2 != 0:
		s1 += '-'
		s2 += '+'
	for i in range(n):
		if s[i] != s1[i]:
			x1 += 1
		elif s[i] != s2[i]:
			x2 += 1
	print(min(x1, x2))


for _ in range(int(input())):
	s = input()
	n = len(s)
	c1 = c2 = 0
	a = '+-' * (n // 2)
	b = '-+' * (n // 2)
	if n % 2 != 0:
		a += '+'
		b += '-'
	for i in range(n):
		if a[i] != s[i]:
			c1 += 1
		elif b[i] != s[i]:
			c2 += 1
	print(min(c1, c2))


def func(s):
	k = s[0]
	c = 0
	for i in range(1, len(s)):
		if i % 2 == 0 and s[i] != k:
			c += 1
		elif i % 2 == 1 and s[i] == k:
			c += 1
	if c < len(s) - c:
		print(c)
	else:
		print(len(s) - c)
for _ in range(int(input())):
	s = input()
	func(s)


def sod(arr):
	ck = 0
	cp = 0
	ak = ['-']
	for i in range(len(arr) - 1):
		if ak[i] == '-':
			ak.append('+')
		else:
			ak.append('-')
	ap = ['+']
	for i in range(len(arr) - 1):
		if ap[i] == '-':
			ap.append('+')
		else:
			ap.append('-')
	for i in range(len(arr)):
		if arr[i] != ak[i]:
			ck += 1
		if arr[i] != ap[i]:
			cp += 1
	return min(cp, ck)
t = int(input())
for i in range(t):
	a = input()
	list1 = []
	for l in a:
		list1.append(l)
	print(sod(list1))


n = int(input())
for i in range(n):
	x = input()
	p = ''
	for j in range(len(x)):
		if j % 2 == 0:
			p = p + '+'
		else:
			p = p + '-'
	q = ''
	for j in range(len(x)):
		if j % 2 == 0:
			q = q + '-'
		else:
			q = q + '+'
	c1 = 0
	c2 = 0
	for j in range(len(x)):
		if x[j] != p[j]:
			c1 = c1 + 1
		if x[j] != q[j]:
			c2 = c2 + 1
	if c1 <= c2:
		print(c1)
	else:
		print(c2)


for _ in range(int(input())):
	s = list(input())
	n = len(s)
	k = n // 2
	if n % 2 == 0:
		p = ['+', '-'] * k
		q = ['-', '+'] * k
	else:
		p = ['+', '-'] * k + ['+']
		q = ['-', '+'] * k + ['-']
	count = 0
	r_count = 0
	for i in range(n):
		if s[i] == p[i]:
			count += 1
		if s[i] == q[i]:
			r_count += 1
	print(min(count, r_count))


l = []
for _ in range(int(input())):
	s = input()
	c = 0
	if s[0] == '+':
		for i in range(1, len(s)):
			if i % 2 == 0:
				if s[i] == '-':
					c += 1
			elif s[i] == '+':
				c += 1
	else:
		for i in range(1, len(s)):
			if i % 2 == 0:
				if s[i] == '+':
					c += 1
			elif s[i] == '-':
				c += 1
	l.append(min(c, len(s) - c))
for i in l:
	print(i)


for _ in range(int(input())):
	s = input()
	cnt1 = 0
	cnt2 = 0
	for j in range(len(s)):
		if j % 2 == 0:
			if s[j] == '+':
				cnt1 += 1
			else:
				cnt2 += 1
		elif s[j] == '-':
			cnt1 += 1
		else:
			cnt2 += 1
	print(min(cnt1, cnt2))