Chef wants to cross a hallway of N doors. These N doors are represented as a string. Each door is initially either open or close, represented by 1 or 0 respectively. Chef is required to go through all the doors one by one in the order that they appear, starting from the leftmost door and moving only rightwards at each step.

To make the journey easier, Chef has a magic wand, using which Chef can flip the status of all the doors at once.
Determine the minimum number of times Chef has to use this wand to cross the hallway of doors.

For example, the doors are 10011. Chef will start from the left and enter the first door. After passing through that door, the magic wand is waved. This flips the string to 01100. Now Chef passes through the next two doors in one go. Again, just before reaching the 4th door, the magic wand is waved. Now that the string is in its original state, Chef passes through the last two doors as well. 
The minimum number of times the magic wand needed to be used here was 2.

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains of a single string S, representing the doors as given in the problem.

------ Output Format ------ 

For each test case, print a single line containing one integer denoting the minimum number of times the magic wand needs to be used.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ |S| ≤ 10^{5}$
- Sum of $|S|$ over all test cases $ ≤ 2 \cdot 10^{6} $

----- Sample Input 1 ------ 
3
111
010
10011
----- Sample Output 1 ------ 
0
3
2
----- explanation 1 ------ 
- Test Case $1$: Since all the doors are already open, Chef doesn't need to use the magic wand at all.
- Test Case $2$: Chef will use the wand the first time to open door $1$. This operation makes the string "101". Chef again needs to use the wand to open door $2$, and then one last time to open door $3$. In total, Chef used the wand $3$ times.
- Testcase $3$: As explained in the problem statement above.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Data structures

Implementation


Solutions:
tc = int(input())
for i in range(tc):
	count = 0
	ed = {'1': True, '0': False}
	st1 = input()
	opnk = ed['1']
	for s in st1:
		if ed[s] == opnk:
			continue
		else:
			opnk = not opnk
			count += 1
	print(count)


test = int(input())
for i in range(test):
	s = input()
	enter = 0
	cnt = 0
	for i in range(len(s)):
		if s[i] == '0' and enter == 0:
			cnt += 1
			enter = 1
		elif s[i] == '1' and enter == 1:
			cnt += 1
			enter = 0
	print(cnt)


for _ in range(int(input())):
	a = input()
	staff_waved = 0
	k = a[0]
	if k == '0':
		staff_waved += 1
	else:
		staff_waved = 0
	for i in a:
		if k != i:
			staff_waved += 1
		k = i
	print(staff_waved)


T = int(input())
for i in range(T):
	s = input()
	k = s[0]
	if k == '0':
		c = 1
	else:
		c = 0
	for i in s:
		if i != k:
			c += 1
			k = i
	print(c)


for i in range(int(input())):
	n = input()
	intial = '1'
	summ = 0
	for i in n:
		if i != intial:
			summ += 1
			intial = i
	print(summ)


for i in range(int(input())):
	n = input()
	a = '1'
	c = 0
	for i in n:
		if i != a:
			c += 1
			a = i
	print(c)


for _ in range(int(input())):
	s = input()
	cur = '1'
	ans = 0
	for i in s:
		if i != cur:
			ans += 1
			cur = i
	print(ans)


for _ in range(int(input())):
	s = list(map(int, input()))
	f = 0
	wand = 0
	a = s
	for i in range(len(s)):
		if a[i] == 0:
			if f == 0:
				f = 1
				wand += 1
		elif a[i] == 1:
			if f == 1:
				f = 0
				wand += 1
	print(wand)


T = int(input())
for _ in range(T):
	S = input()
	waved = 0
	to_not_enter = '0'
	for s in range(len(S)):
		if S[s] == to_not_enter:
			to_not_enter = '0' if to_not_enter == '1' else '1'
			waved += 1
		else:
			continue
	print(waved)


t = int(input())
for i in range(t):
	l = input()
	m = '1'
	c = 0
	for i in range(len(l)):
		if m != l[i]:
			c += 1
			m = l[i]
	print(c)


for _ in range(int(input())):
	l = list(input())
	s = 0
	if l[0] == '0':
		s = 1
	for i in range(len(l) - 1):
		if l[i] != l[i + 1]:
			s = s + 1
	print(s)


for _ in range(int(input())):
	l = input()
	m = '1'
	count = 0
	for i in range(len(l)):
		if m != l[i]:
			count += 1
			m = l[i]
	print(count)


t = int(input())
while t:
	s = input()
	wand = 0
	if s[0] == '0':
		wand = 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			wand += 1
	print(wand)
	t -= 1


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


for i in range(int(input())):
	s = input()
	c = 0
	for j in range(len(s) - 1):
		if s[j] == '0' and s[j + 1] == '1' or (s[j] == '1' and s[j + 1] == '0'):
			c += 1
	if s[0] == '0':
		c += 1
	print(c)


T = int(input())
for i in range(T):
	s = input()
	a = s
	count = 0
	if a[0] == '0':
		count = 1
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			count = count + 1
	print(count)


for _ in range(int(input())):
	a = input()
	c = 0
	for i in range(1, len(a)):
		if a[i] != a[i - 1]:
			c += 1
	if a[0] == '0':
		print(c + 1)
	else:
		print(c)


a = int(input(''))
for i in range(a):
	t = input('')
	k = list(t)
	if k[0] == '0':
		c = 1
	else:
		c = 0
	for j in range(0, len(k) - 1):
		if k[j] != k[j + 1]:
			c = c + 1
	print(c)


for t in range(int(input())):
	s = input()
	c = 0
	d = 1
	for i in range(len(s)):
		if int(s[i]) ^ d == 1:
			c += 1
			d = int(s[i])
	print(c)


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


testcases = int(input())
for i in range(testcases):
	data = input()
	res = 0
	if data[0] == '0':
		res = 1
	for i in range(1, len(data)):
		if data[i] != data[i - 1]:
			res = res + 1
	print(res)


t = int(input())
for _ in range(t):
	s = input()
	ans = 0
	if s[0] == '0':
		ans = 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			ans = ans + 1
	print(ans)


T = int(input())
for _ in range(0, T):
	s = str(input())
	count = 0
	if s[0] == '0':
		count = 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	s = input()
	x = s.split('1')
	count = 0
	if s.count('0') == 0:
		print(0)
	elif s[0] == '0' and s[len(s) - 1] == '0' or (s[0] != '0' and s[len(s) - 1] == '0'):
		for i in range(len(x) - 1):
			if len(x[i]) > 0:
				count += 2
		print(count + 1)
	else:
		for i in range(len(x)):
			if len(x[i]) > 0:
				count += 1
		print(count * 2)


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


for i in range(int(input())):
	s = input()
	c = 1
	if '0' in s:
		x = s.find('0')
	else:
		print(0)
		continue
	for i in range(x, len(s) - 1):
		if s[i] != s[i + 1] and i != len(s) - 1:
			c += 1
	print(c)


t = int(input())
for i in range(t):
	s = input()
	if s[0] != '0':
		print(s.count('10') + s.count('01'))
	else:
		print(s.count('10') + s.count('01') + 1)


t = int(input())
if 1 <= t <= 10 ** 5:
	l = 0

	def flip(_listi):
		count = 0
		_list = []
		_list = _listi
		for count in range(len(_list)):
			if _list[count] == 0:
				_list[count] = 1
			elif _list[count] == 1:
				_list[count] = 0
		return _list
	for _ in range(t):
		l = 0
		arrf = []
		arre = []
		arri = list(map(int, list(input())))
		count = 0
		for count in range(len(arri)):
			if arri[count] == 0:
				arrf.append(1)
			elif arri[count] == 1:
				arrf.append(0)
		arre = arri
		f = 0
		i = 0
		if 1 <= len(arre) <= 10 ** 5:
			for i in range(len(arre)):
				if arre[i] == 0:
					l += 1
					if f == 0:
						arre = arrf
						f = 1
					else:
						arre = arri
						f = 0
		print(l)


def change(x):
	c = 0
	for i in range(len(x) - 1):
		if x[i] != x[i + 1]:
			c += 1
	return c
for _ in range(int(input())):
	s = list(input())
	if s[0] == '0':
		print(change(s) + 1)
	else:
		print(change(s))


T = int(input())
P = []
for i in range(T):
	num = 0
	S = list(input())
	for i in range(len(S)):
		if num % 2 == 0:
			if S[i] == '0':
				num += 1
		elif S[i] == '1':
			num += 1
	P.append(num)
for i in P:
	print(i)


T = int(input())
for i in range(T):
	STR = input()
	Flips = 0
	sign = '0'
	for door in STR:
		if door == sign:
			Flips += 1
			if sign == '0':
				sign = '1'
			else:
				sign = '0'
	print(Flips)


T = int(input())
P = []
for i in range(T):
	num = 0
	S = list(map(int, list(input())))
	L = []
	for i in S:
		if i == 1:
			L.append(0)
		else:
			L.append(1)
	LIST = S
	n = 0
	for i in range(len(S)):
		if n % 2 == 0:
			LIST = S
		else:
			LIST = L
		if LIST[i] == 0:
			num += 1
			LIST = L
			n += 1
	P.append(num)
for i in P:
	print(i)


for _ in range(int(input())):
	s = input()
	cnt = 0
	for i in range(len(s) - 1):
		if s[i] != s[i + 1]:
			cnt += 1
	if s[0] != '0':
		print(cnt)
	else:
		print(cnt + 1)


for tc in range(int(input())):
	s = list(input())
	change = 0
	c = 0
	i = 0
	while i != len(s):
		if change % 2 == 0:
			if s[i] == '0':
				c += 1
				change += 1
		elif s[i] == '1':
			c += 1
			change += 1
		i += 1
	print(c)


for _ in range(int(input())):
	s = input()
	a = s.count('10')
	b = s.count('01')
	if s[0] == '1':
		print(a + b)
	else:
		print(1 + a + b)


T = int(input())
for i in range(T):
	S = input()
	ans = 0
	if S[0] == '0':
		ans += 1
	for i in range(1, len(S)):
		if S[i] != S[i - 1]:
			ans += 1
	print(ans)


T = int(input())
for i in range(T):
	S = input()
	ans = 0
	p = 1
	for i in S:
		if int(i) == p:
			continue
		else:
			p ^= 1
			ans += 1
	print(ans)


T = int(input())
for i in range(T):
	S = input()
	count = 0
	for i in range(len(S)):
		if i == 0 and S[i] == '0':
			count += 1
		elif i > 0 and S[i] != S[i - 1]:
			count += 1
	print(count)


t = int(input())
for _ in range(0, t):
	s = input()
	(j, k) = (0, 0)
	for i in s:
		if j == 0:
			if i == '0':
				k += 1
				j = 1
		elif i == '1':
			k += 1
			j = 0
	print(k)


t = input()
for c in range(0, int(t)):
	s = input()
	count = 0
	flip = 0
	for x in s:
		if x == '0' and flip == 0:
			count = count + 1
			flip = 1
		elif x == '1' and flip == 1:
			count = count + 1
			flip = 0
	print(count)


for _ in range(int(input())):
	s = input()
	c = 0
	if s[0] == '0':
		c = 1
	c1 = s.count('10')
	c2 = s.count('01')
	print(c1 + c2 + c)


for i in range(int(input())):
	s = input()
	count = 0
	for i in s:
		if count % 2 == 0:
			if i == '0':
				count += 1
		elif count % 2 != 0:
			if i == '1':
				count += 1
	print(count)


for i in range(int(input())):
	s = input()
	c = 0
	for j in range(len(s) - 1):
		if s[j] == '0' and s[j + 1] == '1':
			c = c + 1
		elif s[j] == '1' and s[j + 1] == '0':
			c = c + 1
	if s[0] == '0':
		print(c + 1)
	else:
		print(c)


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	nor = s
	flip = ''
	for i in nor:
		if i == '1':
			flip += '0'
		elif i == '0':
			flip += '1'
	s = nor
	for j in range(len(s)):
		if s[j] == '1':
			pass
		elif s[j] == '0':
			count += 1
			if s == nor:
				s = flip
			elif s == flip:
				s = nor
	print(count)


T = int(input())
for _ in range(T):
	string1 = input()
	counter = 0
	flip = 0
	for char in string1:
		if flip == 0:
			if int(char) == 1:
				continue
			else:
				flip = 1
				counter += 1
		elif int(char) == 0:
			continue
		else:
			flip = 0
			counter += 1
	print(counter)


for _ in range(int(input())):
	l = list(map(int, input().strip()))
	cnt = 0
	for i in range(len(l) - 1):
		cur = l[i]
		next = l[i + 1]
		if cur != next:
			cnt += 1
	if l[0] != 1:
		cnt += 1
	print(cnt)


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


for _ in range(int(input())):
	string = input()
	counter = 0
	if string[0] == '0':
		counter += 1
	for i in range(len(string) - 1):
		if string[i] != string[i + 1]:
			counter += 1
	print(counter)


t = int(input())
while t != 0:
	strg = str(input())
	cnt = 0
	if strg[0] == '0':
		cnt += 1
	for i in range(1, len(strg)):
		if strg[-i] != strg[-i - 1]:
			cnt += 1
	print(cnt)
	t -= 1


for _ in range(int(input())):
	s = input()
	c = 0
	for i in range(len(s)):
		if i == 0 and s[i] == '0':
			c += 1
		elif i > 0 and s[i] != s[i - 1]:
			c += 1
	print(c)


t = int(input())
for _ in range(t):
	count = 0
	s = input()
	for i in range(len(s)):
		if i == 0 and s[i] == '0':
			count = count + 1
		elif i > 0 and s[i] != s[i - 1]:
			count = count + 1
	print(count)


T = int(input())
for j in range(T):
	str = input()
	count = 0
	for i in range(len(str)):
		if i == 0 and str[i] == '0':
			count += 1
		elif i > 0 and str[i] != str[i - 1]:
			count += 1
	print(count)


for _ in range(int(input())):
	s = input()
	count = 0
	wand = False
	for i in range(len(s)):
		if s[i] == '0' and wand == False or (s[i] == '1' and wand == True):
			count += 1
			wand = not wand
	print(count)


for x in range(int(input())):
	s = input()
	string = list(s)
	wave = 0
	flag = 0
	for i in range(len(string)):
		if flag == 1:
			if string[i] == '1':
				wave += 1
				flag = 0
		elif string[i] == '0':
			wave += 1
			flag = 1
	print(wave)


t = int(input())
for k in range(t):
	a = str(input())
	b = {'1': '0', '0': '1'}
	c = '0'
	d = 0
	e = 0
	while d != len(a):
		while d != len(a) and a[d] != c:
			d += 1
		e += 1
		c = b[c]
	print(e - 1)


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


for _ in range(int(input())):
	s = input('')
	w = 0
	flag = 0
	for i in range(len(s)):
		if flag == 1:
			if s[i] == '1':
				w += 1
				flag = 0
		elif s[i] == '0':
			w += 1
			flag = 1
	print(w)


t = int(input())
for i in range(t):
	a = input()
	flag = 1
	u = 0
	for j in range(len(a)):
		if flag == 1:
			if a[j] == '0':
				u += 1
				flag = 0
		elif a[j] == '1':
			u += 1
			flag = 1
	print(u)


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]
	(one, zero) = (False, True)
	res = 0
	for ch in s:
		if ch == '0' and zero or (ch == '1' and one):
			(zero, one) = (not zero, not one)
			res += 1
	return res

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='\n')
		else:
			print(res)
main()


for _ in range(int(input())):
	s = input()
	rs = '0'
	tot = 0
	for i in s:
		if i == rs:
			tot = tot + 1
			if rs == '0':
				rs = '1'
			else:
				rs = '0'
	print(tot)


t = int(input())
while t:
	t -= 1
	s = input()
	c = 0
	flag = 0
	for i in range(len(s)):
		if s[i] == '1' and flag == 0:
			continue
		if s[i] == '0' and c % 2 == 0:
			c += 1
			flag = 1
		if s[i] == '1' and c % 2 != 0:
			c += 1
	print(c)


import re
pattern = '((.)\\2*)'
t = int(input())
for i in range(t):
	a = input()
	l = re.findall(pattern, a)
	if a[0] == '1':
		print(len(l) - 1)
	else:
		print(len(l))


t = int(input())
while t:
	t -= 1
	st = input()
	flag = 0
	magic = 0
	for i in range(len(st)):
		if flag == 0 and st[i] == '1':
			pass
		elif flag == 0 and st[i] == '0':
			flag = 1
			magic += 1
		elif flag == 1:
			if magic % 2 == 0:
				if st[i] == '1':
					pass
				else:
					magic += 1
			elif st[i] == '0':
				pass
			else:
				magic += 1
	print(magic)


for t in range(int(input())):
	s = input()
	if s[0] == '1':
		l1 = [i for i in s.split('0')]
		l2 = [i for i in s.split('1')]
		n = len(l1) - l1.count('')
		m = len(l2) - l2.count('')
		print(m + n - 1)
	else:
		l1 = [i for i in s.split('0')]
		l2 = [i for i in s.split('1')]
		n = len(l1) - l1.count('')
		m = len(l2) - l2.count('')
		print(m + n)


t = int(input())
while t >= 1:
	s = input()
	(l, count) = (list(s), 0)
	for j in range(len(s)):
		if count % 2 == 0:
			if l[j] == '0':
				count += 1
		elif l[j] == '1':
			count += 1
	print(count)
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	total = 0
	num = ['0', '1']
	for char in s:
		if char == num[0]:
			total += 1
			num = num[::-1]
	print(total)


tests = int(input())
for i in range(tests):
	string = input()
	count = 0
	for x in string:
		if x == '0':
			if count % 2 == 0:
				count += 1
		elif x == '1':
			if count & 1:
				count += 1
	print(count)


n = int(input())
while n > 0:
	b = input()
	swap = 0
	for i in range(0, len(b)):
		if swap % 2 == 0 and b[i] == '0' or (swap % 2 == 1 and b[i] == '1'):
			swap = swap + 1
	print(swap)
	n = n - 1


for tc in range(int(input())):
	S = input()
	N = len(S)
	if S[0] == '1':
		count = 0
	else:
		count = 1
	for i in range(N - 1):
		if S[i] != S[i + 1]:
			count += 1
	print(count)


t = int(input())
for o in range(t):
	s = str(input())
	o = '1'
	c = 0
	for i in s:
		if i != o:
			c += 1
			if o == '1':
				o = '0'
			else:
				o = '1'
	print(c)