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

You are given a binary string S. You can perform the following operations on S:

Flip: Pick an index i (1 ≤ i ≤ |S|) and flip the i-th character (i.e change 1 to 0 or 0 to 1). For e.g. 01\underline{1}001 \rightarrow 01\underline{0}001
Compress: Pick any non-empty substring consisting of the same character and replace it with a single occurrence of that character. For e.g. 100\underline{1111}10 \rightarrow 100\underline{1}10

You want to make all the characters of the binary string equal (i.e. either all characters are 0 or all characters are 1). Find the minimum number of operations required to do so.

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

- The first line of 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 binary string S.

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

For each test case, output a single line containing one integer - the minimum number of operations required to make all the characters of S equal.

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

$1 ≤T ≤10^{5}$
$1 ≤|S| ≤10^{6}$
$S$ is a binary string.
- It is guaranteed that the sum of $|S|$ over all test cases does not exceed $10^{6}$.

------ subtasks ------ 

Subtask #1 (5 points):
$1 ≤ T ≤ 10^{3}$
$1 ≤ |S| ≤ 10$

Subtask #2 (20 points):
$1 ≤ T ≤ 10^{3}$
$1 ≤ |S| ≤ 50$

Subtask #3 (75 points):
Original constraints

----- Sample Input 1 ------ 
3
100011
1110011
000101110

----- Sample Output 1 ------ 
2
2
3

----- explanation 1 ------ 
In the first test case,

- $1\underline{000}11 \xrightarrow{\text{compress}} 1\underline{0}11$
- $1\underline{0}11 \xrightarrow{\text{flip}} 1\underline{1}11$

In the second test case,

- $111\underline{0}011 \xrightarrow{\text{flip}} 111\underline{1}011$
- $1111\underline{0}11 \xrightarrow{\text{flip}} 1111\underline{1}11$

In the third test case,

- $0001\underline{0}1110 \xrightarrow{\text{flip}} 0001\underline{1}1110$
- $000\underline{11111}0 \xrightarrow{\text{compress}} 000\underline{1}0$
- $000\underline{1}0 \xrightarrow{\text{flip}} 000\underline{0}0$

Difficulty: VERY_HARD
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import re
for _ in range(int(input())):
	x = y = 0
	s = input()
	count0 = count1 = 0
	for i in s:
		if i == '1':
			if count0 > 1:
				x += 2
			elif count0 == 1:
				x += 1
			count1 += 1
			count0 = 0
		else:
			if count1 > 1:
				y += 2
			elif count1 == 1:
				y += 1
			count0 += 1
			count1 = 0
	if count1 > 1:
		y += 2
	elif count1 == 1:
		y += 1
	elif count0 > 1:
		x += 2
	elif count0 == 1:
		x += 1
	flipTrick0 = re.findall('(?=(00(10)+0))', s)
	x -= len(flipTrick0)
	flipTrick1 = re.findall('(?=(11(01)+1))', s)
	y -= len(flipTrick1)
	print(min(x, y))


from sys import stdin
t = int(stdin.readline().rstrip())
while t > 0:
	s = stdin.readline().rstrip()
	(v, ans, n) = (0, 0, len(s))
	i = 0
	flag1 = flag2 = False
	while i < n:
		if s[i] == '0':
			if not flag1:
				flag1 = True
			elif not flag2:
				flag2 = True
		elif flag1:
			if flag2:
				if i < n - 1:
					if s[i + 1] == '0':
						ans += 1
					else:
						ans += 2
						flag1 = False
						flag2 = False
				else:
					ans += 2
					flag1 = False
					flag2 = False
			else:
				ans += 1
				flag1 = False
		i += 1
	if flag1:
		if flag2:
			ans += 2
		else:
			ans += 1
	v = ans
	ans = 0
	i = 0
	flag1 = flag2 = False
	while i < n:
		if s[i] == '1':
			if not flag1:
				flag1 = True
			elif not flag2:
				flag2 = True
		elif flag1:
			if flag2:
				if i < n - 1:
					if s[i + 1] == '1':
						ans += 1
					else:
						ans += 2
						flag1 = False
						flag2 = False
				else:
					ans += 2
					flag1 = False
					flag2 = False
			else:
				ans += 1
				flag1 = False
		i += 1
	if flag1:
		if flag2:
			ans += 2
		else:
			ans += 1
	v = min(v, ans)
	print(v)
	t -= 1


def flip(str, val):
	a = 0
	b = 0
	c = 0
	d = 0
	for i in range(len(str)):
		if str[i] == val:
			c = min(b, c) + 1
			d = min(b, c)
			b = a + 1
			a = a
		else:
			c = min(b, c, d + 1)
			d = min(b, c) + 1
			b = a
			a = a + 1
		a = min(a, b + 1, c + 2, d + 2)
	return a
for i in range(int(input())):
	str = input()
	one = flip(str, '1')
	zero = flip(str, '0')
	print(min(one, zero))


from collections import defaultdict

def flip(s, ch):
	ans = 0
	for i in range(2, len(s) - 2):
		if s[i] == ch and (s[i - 1] != ch and s[i + 1] != ch) and (s[i - 2] != ch or s[i + 2] != ch):
			s[i] = s[i - 1]
			ans += 1
	c = 0
	for i in range(len(s)):
		if s[i] != ch:
			c += 1
		else:
			if c == 1:
				ans += 1
			elif c > 1:
				ans += 2
			c = 0
	if c == 1:
		ans += 1
	if c > 1:
		ans += 2
	return ans
t = int(input())
for _ in range(t):
	s = input()
	s = list(s)
	x = [0] * len(s)
	for i in range(len(s)):
		x[i] = s[i]
	print(min(flip(s, '1'), flip(x, '0')))


import re

def calc(bits):
	zeros = re.findall('(0+)', bits)
	ones = re.findall('(1+)', bits)
	count = [0, 0]
	for zero in zeros:
		count[0] += 2 if len(zero) > 1 else 1
	for one in ones:
		count[1] += 2 if len(one) > 1 else 1
	flipTrick0 = re.findall('(?=(00(10)+0))', bits)
	count[0] -= len(flipTrick0)
	flipTrick1 = re.findall('(?=(11(01)+1))', bits)
	count[1] -= len(flipTrick1)
	return min(count[0], count[1])
for i in range(int(input())):
	print(calc(input()))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()

def pain(s, n, char):
	s1 = list(s)
	res = 0
	for i in range(n):
		if s1[i] != char and s1[i] != '#':
			left = 0
			right = 0
			lid = i - 1
			rid = i + 1
			while lid >= 0 and s1[lid] == char:
				left += 1
				if left > 1:
					break
				lid -= 1
			while rid < n and s1[rid] == char:
				right += 1
				if right > 1:
					break
				rid += 1
			if left > 1 and right > 1 or (left == 1 and right > 1) or (right == 1 and left > 1):
				s1[i] = char
				res += 1
	co = 0
	cur = s1[0]
	for j in range(n):
		if cur == s1[j]:
			co += 1
		else:
			if cur == char:
				res += min(2, co)
			cur = s1[j]
			co = 1
	return res
while t:
	t -= 1
	s = st()
	s = s + '#'
	n = len(s)
	res = min(pain(s, n, '0'), pain(s, n, '1'))
	res = min(s.count('0'), s.count('1'), res)
	ll = []
	co = 0
	cur = s[0]
	for i in s:
		if i == cur:
			co += 1
		else:
			ll.append(co)
			co = 1
			cur = i
	x = 0
	y = 0
	for i in range(len(ll)):
		if i % 2:
			x += min(ll[i], 2)
		else:
			y += min(ll[i], 2)
	res = min(res, x, y)
	print(res)


import sys

class Node:
	__slots__ = ('bit', 'multi', 'l', 'r')

	def __init__(self, bit, multi, l=None, r=None):
		(self.bit, self.multi, self.l, self.r) = (bit, multi, l, r)

	def __repr__(self):
		return f'Node({self.bit}, multi={self.multi})'

def display_list(head, reverse=False):
	ptr = head
	while ptr:
		print(f'{ptr} -> ', end='')
		ptr = ptr.l if reverse else ptr.r
	print('')

def delete_node(n):
	if n.l:
		n.l.r = n.r
	if n.r:
		n.r.l = n.l
	del n

def count_flips(s):
	n = len(s)
	last = None
	for c in s:
		bit = int(int(c))
		if last is None:
			last = Node(bit, False)
		elif bit != last.bit:
			new_node = Node(bit, False)
			new_node.l = last
			last.r = new_node
			last = new_node
		else:
			last.multi = True
	if not last.l:
		return 0
	if not last.l.l:
		if last.multi and last.l.multi:
			return 2
		else:
			return 1
	ops = 0
	head = last.l
	while head.l:
		if head.r and (not head.multi):
			ops += 1
			head = head.l
			head.multi = True
			delete_node(head.r)
			delete_node(head.r)
		else:
			head = head.l
	if not head.r:
		return ops
	if not head.r.r:
		if head.multi and head.r.multi:
			return ops + 2
		else:
			return ops + 1
	ptr = head.r
	while ptr.r:
		if ptr.l and ptr.l.multi:
			ops += 2
			ptr = ptr.r
			ptr.multi = True
			delete_node(ptr.l)
			delete_node(ptr.l)
		else:
			ptr = ptr.r
	if not ptr.l:
		return ops
	if not ptr.l.l:
		if ptr.multi and ptr.l.multi:
			return ops + 2
		else:
			return ops + 1
	return ops + 2
t = int(sys.stdin.readline())
for t_itr in range(t):
	s = sys.stdin.readline().strip()
	res = min(count_flips(s), count_flips(s[::-1]))
	sys.stdout.write(str(res) + '\n')


t = int(input())
for _ in range(t):
	s = input()
	l1 = len(s)
	list_of_ones = []
	end1 = 0
	end2 = 0
	count = 0
	cost = 0
	if l1 > 1:
		for i in range(l1):
			if i == l1 - 1 or s[i] != s[i + 1]:
				count += 1
			if i == 0 and s[i] != s[i + 1]:
				end1 += 1
			elif i == l1 - 1 and s[i] != s[i - 1]:
				end2 += 1
			elif s[i] != s[i - 1] and s[i] != s[i + 1]:
				list_of_ones.append(count)
	l2 = len(list_of_ones)
	count_end1 = 0
	i1 = 0
	while i1 <= l2 - 1:
		if list_of_ones[i1] - i1 != 2:
			break
		count_end1 += 1
		i1 += 1
	if count_end1 % 2 == 1:
		end1 = 0
	count_end2 = 0
	j = -1
	while j >= -l2:
		if list_of_ones[j] - j != count:
			break
		count_end2 += 1
		j -= 1
	if count_end2 % 2 == 1:
		end2 = 0
	counter = 0
	if l2 == 1:
		count -= 2
		cost += 1
	else:
		for i in range(l2):
			if i == 0 and list_of_ones[i + 1] - list_of_ones[i] != 1 or (i == l2 - 1 and list_of_ones[i] - list_of_ones[i - 1] != 1) or (list_of_ones[i] - list_of_ones[i - 1] != 1 and list_of_ones[i + 1] - list_of_ones[i] != 1):
				cost += 1
				count -= 2
			if i != l2 - 1 and list_of_ones[i + 1] - list_of_ones[i] == 1:
				cost += 0.5
				count -= 1
				counter += 1
			elif list_of_ones[i] - list_of_ones[i - 1] == 1 and i == l2 - 1 or (i != 0 and list_of_ones[i] - list_of_ones[i - 1] == 1 and (list_of_ones[i + 1] - list_of_ones[i] != 1)):
				counter += 1
				if counter % 2 == 0:
					cost += 0.5
					count -= 1
					counter = 0
				else:
					cost += 1
					count -= 2
					counter = 0
	ends = end1 + end2
	if count % 2 == 1:
		cost += count - 1
	elif ends == 0:
		cost += count
	else:
		cost += count - 1
	print(int(cost))


def solve(X):
	X.append(-1337)
	S = [-1337, X[0]]
	ret = 0
	i = 1
	while i < len(X) - 1:
		if X[i] == 1 and S[-1] > 1:
			if X[i + 1] != -1337:
				S[-1] = 9
				ret += 1
				i += 2
			else:
				S.append(1)
				i += 1
		elif X[i] == 1 and S[-1] == 1:
			S.append(1)
			i += 1
		elif X[i] > 1 and S[-1] == 1:
			while S[-1] == 1 and S[-2] != -1337:
				S.pop()
				S.pop()
				ret += 1
			S.append(9)
			i += 1
		elif X[i] > 1 and S[-1] > 1:
			S.append(X[i])
			i += 1
	S.pop(0)
	if len(S) % 2 == 0 and S[0] == 1:
		S.pop(0)
		S[0] += 1
		ret += 1
	elif len(S) % 2 == 0 and S[-1] == 1:
		S.pop()
		S[-1] += 1
		ret += 1
	if len(S) == 3:
		return ret + 2
	if S.count(1) == len(S):
		return ret + len(S) // 2
	ret += 2 * (len(S) // 2)
	return ret

def convert(S):
	S += '#'
	i = 0
	ret = []
	for j in range(1, len(S)):
		if S[j] != S[i]:
			ret.append(j - i)
			i = j
	return ret
for _ in range(int(input())):
	S = input()
	print(min(solve(convert(S)), S.count('1'), S.count('0')))


for _ in range(int(input())):
	s = input()
	(v, ans, n) = (0, 0, len(s))
	i = 0
	flag = flag2 = False
	while i < n:
		if s[i] == '0':
			if not flag:
				flag = True
			elif not flag2:
				flag2 = True
		elif flag:
			if flag2:
				if i < n - 1:
					if s[i + 1] == '0':
						ans += 1
					else:
						ans += 2
						flag = False
						flag2 = False
				else:
					ans += 2
					flag = False
					flag2 = False
			else:
				ans += 1
				flag = False
		i += 1
	if flag:
		if flag2:
			ans += 2
		else:
			ans += 1
	v = ans
	ans = 0
	i = 0
	flag = flag2 = False
	while i < n:
		if s[i] == '1':
			if not flag:
				flag = True
			elif not flag2:
				flag2 = True
		elif flag:
			if flag2:
				if i < n - 1:
					if s[i + 1] == '1':
						ans += 1
					else:
						ans += 2
						flag = False
						flag2 = False
				else:
					ans += 2
					flag = False
					flag2 = False
			else:
				ans += 1
				flag = False
		i += 1
	if flag:
		if flag2:
			ans += 2
		else:
			ans += 1
	v = min(v, ans)
	print(v)


t = int(input())
while t:
	t = t - 1
	string = input()
	count = 1
	modStr = string
	change = 1
	ops = 0
	(s0, s1, d0, d1) = (0, 0, 0, 0)
	while change:
		backup = modStr
		ops += modStr.count('1101')
		modStr = modStr.replace('1101', '1111')
		ops += modStr.count('1011')
		modStr = modStr.replace('1011', '1111')
		change = backup != modStr
	lastSeen = modStr[0]
	for i in range(1, len(string)):
		if modStr[i] == lastSeen:
			count += 1
		else:
			if count > 1:
				if lastSeen == '0':
					d0 += 1
				else:
					d1 += 1
				count = 1
			else:
				if lastSeen == '0':
					s0 += 1
				else:
					s1 += 1
				count = 1
			lastSeen = modStr[i]
	if count > 1:
		if lastSeen == '0':
			d0 += 1
		else:
			d1 += 1
	elif lastSeen == '0':
		s0 += 1
	else:
		s1 += 1
	ops1 = ops + min(s0 + d0 * 2, s1 + d1 * 2)
	count = 1
	modStr = string
	change = 1
	ops = 0
	(s0, s1, d0, d1) = (0, 0, 0, 0)
	while change:
		backup = modStr
		ops += modStr.count('0010')
		modStr = modStr.replace('0010', '0000')
		ops += modStr.count('0100')
		modStr = modStr.replace('0100', '0000')
		change = backup != modStr
	lastSeen = modStr[0]
	for i in range(1, len(string)):
		if modStr[i] == lastSeen:
			count += 1
		else:
			if count > 1:
				if lastSeen == '0':
					d0 += 1
				else:
					d1 += 1
				count = 1
			else:
				if lastSeen == '0':
					s0 += 1
				else:
					s1 += 1
				count = 1
			lastSeen = modStr[i]
	if count > 1:
		if lastSeen == '0':
			d0 += 1
		else:
			d1 += 1
	elif lastSeen == '0':
		s0 += 1
	else:
		s1 += 1
	ops2 = ops + min(s0 + d0 * 2, s1 + d1 * 2)
	print(min(ops1, ops2))


T = int(input())
for _ in range(T):
	st = input()
	str0_1 = st
	str1_0 = st
	flag0_1 = True
	flag1_0 = True
	count0_1 = 0
	count1_0 = 0
	(s00, s10, d00, d10) = (0, 0, 0, 0)
	(s01, s11, d01, d11) = (0, 0, 0, 0)
	(s0, d0, s1, d1) = (0, 0, 0, 0)
	flag = 0
	flag1 = 0
	flag2 = 0
	if len(st) == 1:
		print(0)
		continue
	while flag0_1:
		if '1101' in str0_1 or '1011' in str0_1:
			if '1101' in str0_1:
				count0_1 += str0_1.count('1101')
				str0_1 = str0_1.replace('1101', '1111')
			else:
				count0_1 += str0_1.count('1011')
				str0_1 = str0_1.replace('1011', '1111')
		else:
			flag0_1 = False
	while flag1_0:
		if '0010' in str1_0 or '0100' in str1_0:
			if '0010' in str1_0:
				count1_0 += str1_0.count('0010')
				str1_0 = str1_0.replace('0010', '0000')
			else:
				count1_0 += str1_0.count('0100')
				str1_0 = str1_0.replace('0100', '0000')
		else:
			flag1_0 = False
	for i in range(1, len(str0_1)):
		if str0_1[i] == str0_1[i - 1]:
			flag2 = 1
		elif str0_1[i - 1] == '0' and flag2 == 0:
			s00 += 1
			flag2 = 0
		elif str0_1[i - 1] == '0' and flag2 == 1:
			d00 += 1
			flag2 = 0
		elif str0_1[i - 1] == '1' and flag2 == 0:
			s10 += 1
			flag2 = 0
		elif str0_1[i - 1] == '1' and flag2 == 1:
			d10 += 1
			flag2 = 0
	if str0_1[-1] == str0_1[-2]:
		if str0_1[-1] == '0':
			d00 += 1
		else:
			d10 += 1
	elif str0_1[-1] == '0':
		s00 += 1
	else:
		s10 += 1
	for i in range(1, len(str1_0)):
		if str1_0[i] == str1_0[i - 1]:
			flag1 = 1
		elif str1_0[i - 1] == '0' and flag1 == 0:
			s01 += 1
			flag1 = 0
		elif str1_0[i - 1] == '0' and flag1 == 1:
			d01 += 1
			flag1 = 0
		elif str1_0[i - 1] == '1' and flag1 == 0:
			s11 += 1
			flag1 = 0
		elif str1_0[i - 1] == '1' and flag1 == 1:
			d11 += 1
			flag1 = 0
	if str1_0[-1] == str1_0[-2]:
		if str1_0[-1] == '0':
			d01 += 1
		else:
			d11 += 1
	elif str1_0[-1] == '0':
		s01 += 1
	else:
		s11 += 1
	to_0_0 = count0_1 + s00 + 2 * d00
	to_1_0 = count0_1 + s10 + 2 * d10
	to_0_1 = count1_0 + s01 + 2 * d01
	to_1_1 = count1_0 + s11 + 2 * d11
	print(min(to_0_0, to_1_0, to_0_1, to_1_1))


def readInt():
	return int(input())

def readInts():
	return [int(x) for x in input().split()]

def readString():
	return input().rstrip()

def readStrings():
	return input().split()

def printList(l):
	return ' '.join((str(x) for x in l))

def readCase():
	bin_string = readString()
	return bin_string

def solve_target(bin_string, target, other):
	blocks = bin_string.count(other + target) + bin_string.startswith(target)
	(pos, large_blocks) = (0, 0)
	while True:
		pos = bin_string.find(2 * target, pos)
		if pos == -1:
			break
		pos = bin_string.find(2 * other, pos)
		large_blocks += 1
		if pos == -1:
			break
	return blocks + large_blocks

def solve(bin_string):
	return min(solve_target(bin_string, '0', '1'), solve_target(bin_string, '1', '0'))
cases = readInt()
for case in range(cases):
	print(solve(readCase()))


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
sys.setrecursionlimit(10 ** 8)
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	s = list(ip())
	ans = float('inf')
	for j in range(2):
		b = []
		c = []
		b.append(s[0])
		c.append(1)
		for i in range(1, len(s)):
			if s[i] == s[i - 1]:
				c[-1] += 1
			else:
				b.append(s[i])
				c.append(1)
		tot = 0
		for i in range(len(b)):
			if b[i] == '1':
				continue
			elif i == 0:
				continue
			elif c[i] > 1:
				continue
			elif i == len(b) - 1:
				continue
			else:
				t = c[i - 1] + c[i + 1]
				if t == 2:
					continue
				else:
					tot += 1
					c[i + 1] = t + 1
					c[i - 1] = 0
					b[i - 1] = '0'
		for i in range(len(b)):
			if b[i] == '1':
				if c[i] == 1:
					tot += 1
				else:
					tot += 2
		ans = min(ans, tot)
		for i in range(len(s)):
			if s[i] == '1':
				s[i] = '0'
			else:
				s[i] = '1'
	print(ans)


from sys import stdin
input = stdin.readline

def flipsemideepsingles(S):
	count = 0
	for i in range(2, len(S) - 1):
		if S[i - 2] == S[i - 1] and S[i - 1] != S[i] and (S[i] != S[i + 1]):
			count += 1
			S[i] = S[i - 1]
	for i in reversed(range(1, len(S) - 2)):
		if S[i - 1] != S[i] and S[i] != S[i + 1] and (S[i + 1] == S[i + 2]):
			count += 1
			S[i] = S[i + 1]
	return (S, count)

def flipsingle(S, flip):
	count = 0
	for i in range(1, len(S) - 1):
		if S[i] == flip and S[i - 1] != S[i] and (S[i] != S[i + 1]):
			count += 1
			S[i] = S[i - 1]
	return (S, count)

def compressflip(S, flip):
	if S[0] == flip:
		first = [0]
	else:
		first = []
	for i in range(1, len(S)):
		if S[i] == flip and S[i] != S[i - 1]:
			first.append(i)
	last = []
	for i in range(len(S) - 1):
		if S[i] == flip and S[i] != S[i + 1]:
			last.append(i)
	if S[len(S) - 1] == flip:
		last.append(len(S) - 1)
	count = 0
	for (a, b) in zip(first, last):
		if a == b:
			count += 1
		else:
			count += 2
	return count

def solve(S):
	(S, count) = flipsemideepsingles([int(s) for s in S])
	(S0, count0) = (list(S), count)
	(S1, count1) = (list(S), count)
	(S0, count) = flipsingle(S0, 0)
	count0 += count
	count = compressflip(S0, 0)
	count0 += count
	(S1, count) = flipsingle(S1, 1)
	count1 += count
	count = compressflip(S1, 1)
	count1 += count
	return min(count0, count1)
T = int(input().strip())
for problem in range(1, T + 1):
	S = input().strip()
	print(solve(S))


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
x = 0
pref = []
lvl = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot
prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def func(a):
	stck = []
	last = 1
	c = 0
	for i in a:
		if i == '0':
			if c != 0:
				stck.append(c)
			stck.append(0)
			c = 0
		else:
			c += 1
	if c != 0:
		stck.append(c)
	tot = []
	for i in range(len(stck)):
		if stck[i] == 0:
			continue
		if len(tot) > 0 and i - 2 >= 0 and (stck[i - 2] != 0):
			if stck[i] == 1:
				if tot[-1][0] > 1:
					tot[-1][0] += stck[i]
					tot[-1][1] += 1
				else:
					tot.append([stck[i], 0])
			else:
				tot[-1][0] += stck[i]
				tot[-1][1] += 1
		else:
			tot.append([stck[i], 0])
	ans = 0
	for (i, j) in tot:
		ans += 1 + (i > 1) + j
	return ans

def hnbhai(tc):
	a = sa()
	b = []
	for i in a:
		if i == '0':
			b.append('1')
		else:
			b.append('0')
	print(min(func(a), func(b)))
for _ in range(sb()):
	hnbhai(_ + 1)


def solve():
	org = input()
	make0 = [[float('inf'), float('inf'), float('inf')] for i in range(len(org) + 1)]
	make1 = [[float('inf'), float('inf'), float('inf')] for i in range(len(org) + 1)]
	make0[0][0] = 0
	make1[0][0] = 0
	for i in range(1, len(org) + 1):
		if org[i - 1] == '0':
			make0[i][0] = min(make0[i - 1][0], make0[i - 1][1] + 1, make0[i - 1][2] + 2)
			make0[i][1] = min(make0[i - 1][0], make0[i - 1][2] + 2) + 1
			make0[i][2] = min(make0[i - 1][2], make0[i - 1][1]) + 1
			make1[i][0] = min(make1[i - 1][0] + 1, make1[i - 1][1] + 2, make1[i - 1][2] + 2)
			make1[i][1] = min(make1[i - 1][0], make1[i - 1][2] + 2)
			make1[i][2] = min(make1[i - 1][2], make1[i - 1][1])
		else:
			make0[i][0] = min(make0[i - 1][0] + 1, make0[i - 1][1] + 2, make0[i - 1][2] + 2)
			make0[i][1] = min(make0[i - 1][0], make0[i - 1][2] + 2)
			make0[i][2] = min(make0[i - 1][2], make0[i - 1][1])
			make1[i][0] = min(make1[i - 1][0], make1[i - 1][1] + 1, make1[i - 1][2] + 2)
			make1[i][1] = min(make1[i - 1][0], make1[i - 1][2] + 2) + 1
			make1[i][2] = min(make1[i - 1][2], make1[i - 1][1]) + 1
	return min(make0[len(org)][0], make1[len(org)][0])
remaiend_test_cases = 1
remaiend_test_cases = int(input())
while remaiend_test_cases > 0:
	print(solve())
	remaiend_test_cases -= 1


def cnt(s, one):
	c1p = 0
	c1p0 = 0
	c1p00p = 0
	c1p0p1 = 0
	for i in range(0, len(s)):
		if s[i] == one:
			c1p00p = min(c1p0, c1p00p) + 1
			c1p0p1 = min(c1p0, c1p00p)
			c1p0 = c1p + 1
			c1p = c1p
		else:
			c1p00p = min(c1p0, c1p00p, c1p0p1 + 1)
			c1p0p1 = min(c1p0, c1p00p) + 1
			c1p0 = c1p
			c1p = c1p + 1
		c1p = min(c1p, c1p0 + 1, c1p00p + 2, c1p0p1 + 2)
	return c1p
N = int(input())
for i in range(N):
	s = input()
	one = cnt(s, '1')
	zero = cnt(s, '0')
	print(min(one, zero))


import re
import sys
from functools import reduce
from collections import deque
import random
from heapq import heappop, heappush
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
printf = lambda x: sys.stdout.write(str(x))

def seqtotuple(s):
	arr = [1]
	p = 0
	for i in range(1, len(s)):
		if s[i] != s[p]:
			p = i
			arr.append(0)
		arr[-1] += 1
	return tuple(arr)

def getcont(s):
	arr = []
	c = 0
	for i in range(1, len(s) - 1):
		if s[i] == 1:
			c += 1
		if s[i] != 1 and c > 0:
			arr.append(c)
			c = 0
	if c:
		arr.append(c)
	return arr

def smart(s):
	if len(s) == 1:
		return 0
	if len(s) == 2:
		return 1 if s[0] == 1 or s[1] == 1 else 2
	arr = []
	arr = getcont(s)
	t = sum([e // 2 + e % 2 for e in arr])
	k = len(s) - 2 * t
	return t + k - k % 2 - ((s[0] == 1 and s[1] != 1 or (s[0] == s[1] == 1 and arr[0] % 2 == 0) or (s[-1] == s[-2] == 1 and arr[-1] % 2 == 0) or (s[-1] == 1 and s[-2] != 1)) and k % 2 == 0)
t = int(input())
for _ in range(t):
	s = input().strip()
	seq = seqtotuple(s)
	printf(smart(seq))
	printf('\n')


from sys import stdin

def get_answer(S):
	if len(S) == 1:
		return 0
	ones = [0, 0]
	zeros = [0, 0]
	(prev, old_prev) = (S[0], -1)
	(cnt, old_cnt) = (1, 0)
	ext = 0
	for x in S[1:]:
		if x == prev:
			cnt += 1
			continue
		if cnt == 1 and old_cnt > 0:
			if old_prev == '1':
				ones[0] -= 1
				if old_cnt > 1:
					ones[1] -= 1
			if old_prev == '0':
				zeros[0] -= 1
				if old_cnt > 1:
					zeros[1] -= 1
			prev = old_prev
			cnt = old_cnt + 1
			ext += 1
			continue
		if prev == '1':
			ones[0] += 1
			if cnt > 1:
				ones[1] += 1
			(old_prev, prev) = (prev, x)
			(old_cnt, cnt) = (cnt, 1)
		elif prev == '0':
			zeros[0] += 1
			if cnt > 1:
				zeros[1] += 1
			(old_prev, prev) = (prev, x)
			(old_cnt, cnt) = (cnt, 1)
		else:
			prev = x
			cnt = 1
	if prev == '1':
		ones[0] += 1
		if cnt > 1:
			ones[1] += 1
		prev = x
		cnt = 1
	else:
		zeros[0] += 1
		if cnt > 1:
			zeros[1] += 1
		prev = x
		cnt = 1
	return min(sum(ones), sum(zeros)) + ext

def solve():
	results = []
	for _ in range(int(stdin.readline().rstrip())):
		S = stdin.readline().rstrip()
		results.append(min(get_answer(S), get_answer(S[::-1])))
	print('\n'.join(map(str, results)))
solve()


for _ in range(int(input())):
	s = input()
	h = []
	i = 0
	while i < len(s):
		if s[i] == '0' and i + 1 < len(s) and (s[i + 1] == '0'):
			h.append('a')
			while i < len(s) and s[i] == '0':
				i += 1
			continue
		elif s[i] == '0' and (i + 1 < len(s) and s[i + 1] == '1' or i + 1 >= len(s)):
			h.append('d')
			i += 1
			continue
		elif s[i] == '1' and i + 1 < len(s) and (s[i + 1] == '1'):
			h.append('c')
			while i < len(s) and s[i] == '1':
				i += 1
			continue
		else:
			h.append('b')
			i += 1
			continue
	c1 = 0
	i = 0
	while i < len(h):
		if h[i] == 'a':
			if i + 2 < len(h) and h[i + 1] == 'b' and (h[i + 2] == 'a' or h[i + 2] == 'd'):
				c1 += 2
				while i + 2 < len(h) and h[i + 1] == 'b' and (h[i + 2] == 'a' or h[i + 2] == 'd'):
					c1 += 1
					i += 2
				i += 1
			else:
				c1 += 2
				i += 1
		elif h[i] == 'd':
			c1 += 1
			i += 1
		else:
			i += 1
	c0 = 0
	i = 0
	while i < len(h):
		if h[i] == 'c':
			if i + 2 < len(h) and h[i + 1] == 'd' and (h[i + 2] == 'c' or h[i + 2] == 'b'):
				c0 += 2
				while i + 2 < len(h) and h[i + 1] == 'd' and (h[i + 2] == 'c' or h[i + 2] == 'b'):
					c0 += 1
					i += 2
				i += 1
			else:
				c0 += 2
				i += 1
		elif h[i] == 'b':
			c0 += 1
			i += 1
		else:
			i += 1
	print(min(c0, c1))


def fun(s):
	n = len(s)
	s = ['k'] + s + ['k']
	i = 1
	ans = 0
	while i < n + 1:
		if s[i] == '0':
			if s[i - 1] != '0' and s[i + 1] != '0':
				ans += 1
			else:
				while s[i] == '0':
					i += 1
				c = 0
				if i == n + 1:
					ans += 2
					break
				while s[i] == '1':
					i += 1
					c += 1
				if i == n + 1:
					ans += 2
					break
				if c == 1:
					s[i - 1] = '0'
					ans += 1
					i -= 2
				else:
					ans += 2
					i -= 1
		i += 1
	return ans

def f1(s):
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			s[i] = '0'
		else:
			s[i] = '1'
	return fun(s)
t = int(input())
while t > 0:
	t -= 1
	s = [i for i in input()]
	x = fun(s)
	y = f1(s)
	print(min(x, y))


def _find_consecutive_one_intervals(s):
	s = s + '0'
	windows = []
	(l, r) = (0, 0)
	for (r, rc) in enumerate(s):
		if rc == '1':
			continue
		while r > l and s[l] == '0':
			l += 1
		if l == r:
			continue
		windows.append((l, r))
		l = r
	return windows

def all_zeros(s):
	if s.count('0') == len(s):
		return 0
	if s.count('1') == len(s):
		return min(len(s), 2)
	windows = _find_consecutive_one_intervals(s)
	res = 0
	consecutive_windows = [[windows[0]]]
	for (left, right) in windows[1:]:
		cur_window = (left, right)
		(prev_left, prev_right) = consecutive_windows[-1][-1]
		if left - prev_right == 1:
			consecutive_windows[-1].append(cur_window)
		else:
			consecutive_windows.append([cur_window])
	res = 0
	for cons_windo in consecutive_windows:
		if all((r - l == 1 for (l, r) in cons_windo)):
			res += len(cons_windo)
		else:
			res += len(cons_windo) + 1
	return res
num_tests = int(input())
for _ in range(num_tests):
	s = input()
	zeros = all_zeros(s)
	ones = all_zeros(s.replace('0', '2').replace('1', '0').replace('2', '1'))
	print(min(zeros, ones))


import sys
import re

def calc(bits):
	zeros = re.findall('(0+)', bits)
	ones = re.findall('(1+)', bits)
	count = [0, 0]
	for zero in zeros:
		count[0] += 2 if len(zero) > 1 else 1
	for one in ones:
		count[1] += 2 if len(one) > 1 else 1
	flipTrick0 = re.findall('(?=(00(10)+0))', bits)
	count[0] -= len(flipTrick0)
	flipTrick1 = re.findall('(?=(11(01)+1))', bits)
	count[1] -= len(flipTrick1)
	return min(count[0], count[1])
firstInput = True
for line in sys.stdin:
	if firstInput:
		firstInput = False
		continue
	numbers = line.split('\n')[0]
	print(str(calc(numbers)))