You are given a string $s$ consisting of characters 0 and/or 1.

You have to remove several (possibly zero) characters from the beginning of the string, and then several (possibly zero) characters from the end of the string. The string may become empty after the removals. The cost of the removal is the maximum of the following two values:

the number of characters 0 left in the string;

the number of characters 1 removed from the string.

What is the minimum cost of removal you can achieve?


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line containing the string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of characters 0 and/or 1.

The total length of strings $s$ in all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print one integer — the minimum cost of removal you can achieve.


-----Examples-----

Input
5
101110110
1001001001001
0000111111
00000
1111
Output
1
3
0
0
0


-----Note-----

Consider the test cases of the example:

in the first test case, it's possible to remove two characters from the beginning and one character from the end. Only one 1 is deleted, only one 0 remains, so the cost is $1$;

in the second test case, it's possible to remove three characters from the beginning and six characters from the end. Two characters 0 remain, three characters 1 are deleted, so the cost is $3$;

in the third test case, it's optimal to remove four characters from the beginning;

in the fourth test case, it's optimal to remove the whole string;

in the fifth test case, it's optimal to leave the string as it is.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Amortized analysis

Greedy algorithms
Skill types: Sorting

Amortized analysis

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline

def solve():
	s = input().strip()
	n = len(s)
	curr = 0
	prefixCount = [0]
	for i in range(n):
		if s[i] == '0':
			curr += 1
		prefixCount.append(curr)
	cnt = [curr, n - curr]
	ans = float('inf')
	for i in range(curr + 1):
		ans = min(ans, prefixCount[i + cnt[1]] - prefixCount[i])
	return ans
for _ in range(int(input())):
	print(solve())


def mincost(s):
	n = len(s)
	nums1 = s.count('1')
	n0 = 0
	for i in range(nums1):
		if s[i] == '0':
			n0 += 1
	res = n0
	for j in range(nums1, n):
		if s[j] == '0':
			n0 += 1
		if s[j - nums1] == '0':
			n0 -= 1
		res = min(res, n0)
	return res
t = int(input())
for _ in range(t):
	s = input()
	res = mincost(s)
	print(res)


t = int(input())
ans = []
for x in range(t):
	s = input()
	n = len(s)
	zi = 0
	numz = {}
	numz[-1] = 0
	for x in range(n):
		if s[x] == '0':
			zi = zi + 1
		numz[x] = zi
	winsize = n - zi
	cost = numz[winsize - 1] - numz[-1]
	for x in range(-1, n - winsize):
		cost = min(cost, numz[x + winsize] - numz[x])
	ans.append(cost)
for a in ans:
	print(a)


import math
for _ in range(int(input())):
	s = input()
	n = len(s)
	zi = 0
	numz = {}
	numz[0] = 0
	for x in range(n):
		if s[x] == '0':
			zi = zi + 1
		numz[x + 1] = zi
	ones = n - zi
	cost = math.inf
	for x in range(zi + 1):
		cost = min(cost, numz[x + ones] - numz[x])
	print(cost)


t = int(input())
for i in range(t):
	s = list(map(int, list(input())))
	n = len(s)
	b = 0
	for i in s:
		if i == 1:
			b += 1
	l = 0
	r = b
	if r == 0:
		print(0)
		continue
	cur = 0
	for i in range(l, r):
		if s[i] == 0:
			cur += 1
	ans = cur
	while r < n:
		if r < n and s[r] == 0:
			cur += 1
		if s[l] == 0:
			cur -= 1
		if cur < ans:
			ans = cur
		l += 1
		r += 1
	print(ans)


class Solution:

	def helper(self, s, x):
		n = len(s)
		dp = [0] * (x + 1)
		l = 0
		for i in s:
			if i == '1':
				l += 1
				dp[l] = dp[l - 1]
			else:
				dp[l] += 1
		return dp

	def solve(self):
		s = input()
		n = len(s)
		x = s.count('0')
		ans = min(x, n - x)
		dp_front = self.helper(s, n - x)
		dp_back = self.helper(s[::-1], n - x)
		i = 0
		while i < ans:
			j = ans - i - 1
			while j >= 0 and x - (dp_front[i] + dp_back[j]) < ans:
				ans = max(i + j, x - (dp_front[i] + dp_back[j]))
				j -= 1
			i += 1
		return ans
for i in range(int(input())):
	print(Solution().solve())


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	ones = [0] * (n + 1)
	for i in range(n):
		ones[i + 1] = ones[i]
		if s[i] == '1':
			ones[i + 1] += 1
	x = ones[-1]
	res = 1000000000.0
	for i in range(x, n + 1):
		res = min(res, x - ones[i] + ones[i - x])
	print(res)


for x in range(int(input())):
	a = list(input())
	b = a.count('1')
	y = [a[0:b].count('0')]
	m = a[0:b].count('0')
	for i in range(0, len(a) - b):
		m += int(a[i]) - int(a[i + b])
		y.append(m)
	print(min(y))


a = int(input())
for y in range(a):
	b = input()
	q = len(b) - 1
	c = b.count('1')
	d = b.count('0')
	if c == 0 or d == 0:
		print(0)
	else:
		o = b[:d].count('1')
		z = b[:d].count('0')
		ans = max(d - z, o)
		for y in range(d - 1, -1, -1):
			if b[y] == '1':
				o -= 1
			else:
				z -= 1
			if b[q] == '1':
				o += 1
			else:
				z += 1
			q -= 1
			ans = min(ans, max(d - z, o))
		print(ans)


t = int(input())
for z in range(t):
	s = input()
	n = len(s)
	arr = [0]
	for i in range(n):
		arr.append(arr[-1] + int(s[i]))
	ans = n - arr[-1]
	for i in range(n - arr[-1] + 1):
		j = i + arr[-1]
		ans = min(ans, arr[-1] - (arr[j] - arr[i]))
	print(ans)


for inh in range(int(input())):
	s = input()
	n = len(s)
	zer = s.count('0')
	k = zer
	a = [0]
	for i in s:
		a.append(a[-1] + int(i))
	for i in range(zer + 1):
		dd = i + a[-1]
		k = min(k, a[-1] - (a[dd] - a[i]))
	print(k)


r = int(input())
for p in range(r):
	u = input()
	n = len(u)
	k = [0]
	for i in range(n):
		k.append(k[-1] + int(u[i]))
	ans = n - k[-1]
	for i in range(n - k[-1] + 1):
		j = i + k[-1]
		ans = min(ans, k[-1] - (k[j] - k[i]))
	print(ans)


import sys

def minimise(string):
	s = 0
	for i in string:
		s += 1 if i == '1' else 0
	(num0, num1) = (0, s)
	j = 0
	ans = sys.maxsize
	for i in range(len(string)):
		if string[i] == '0':
			num0 += 1
		else:
			num1 -= 1
		while num1 < num0:
			if string[j] == '1':
				num1 += 1
			else:
				num0 -= 1
			j += 1
			ans = min(ans, max(num0, num1))
		ans = min(ans, max(num0, num1))
	return ans
t = int(input())
while t:
	s = input()
	print(minimise(s))
	t -= 1


import sys

def solve():
	for tc in range(int(input())):
		s = list(input())
		n = len(s)
		num0 = 0
		for i in s:
			if i == '0':
				num0 += 1
		(pre0, pre0r) = ([], [])
		(z, zr) = (0, 0)
		for i in range(n):
			if s[i] == '0':
				z += 1
			if s[n - i - 1] == '0':
				zr += 1
			pre0.append(z)
			pre0r.append(zr)
		if num0 == 0 or num0 == n:
			print(0)
		else:
			ans = sys.maxsize
			for i in range(-1, num0):
				zrem = 0
				if i != -1:
					zrem += pre0[i]
				if i != num0 - 1:
					zrem += pre0r[num0 - i - 2]
				orem = num0 - zrem
				ans = min(ans, orem)
			print(ans)
solve()


z = int(input())
for kvs in range(z):
	s = input()
	n = len(s)
	b = s.count('0')
	k = b
	a = [0]
	for i in s:
		a.append(a[-1] + int(i))
	for i in range(b + 1):
		d = i + a[-1]
		k = min(k, a[-1] - (a[d] - a[i]))
	print(k)


def can(pos, k):
	c = len(pos)
	num1 = c - k
	for i in range(k + 1):
		x1 = pos[i]
		x2 = pos[i + num1 - 1]
		if x2 - x1 + 1 - num1 <= k:
			return True
	return False
T = int(input())
while T:
	T -= 1
	s = input().strip('0')
	pos = []
	for i in range(len(s)):
		if s[i] == '1':
			pos.append(i)
	l = 0
	r = len(pos) - 1
	while l <= r:
		mid = (r + l) // 2
		if can(pos, mid):
			r = mid - 1
		else:
			l = mid + 1
	print(l)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def isPossible(mid, pref, suff, zeros):
	for i in range(mid + 1):
		zeros_left = zeros
		ones_rem_L = pref[i]
		ones_rem_R = suff[mid - i]
		zeros_left -= ones_rem_L + ones_rem_R
		if zeros_left <= mid:
			return True
	return False

def solve():
	s = input()
	zeros = s.count('0')
	ones = s.count('1')
	pref = []
	suff = []
	count = 0
	for i in range(len(s)):
		if s[i] == '0':
			count += 1
		else:
			pref.append(count)
	pref.append(count)
	count = 0
	for j in range(len(s) - 1, -1, -1):
		if s[j] == '0':
			count += 1
		else:
			suff.append(count)
	suff.append(count)
	low = 0
	high = ones
	ans = -1
	while low <= high:
		mid = (low + high) // 2
		if isPossible(mid, pref, suff, zeros):
			ans = mid
			high = mid - 1
		else:
			low = mid + 1
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1


import sys
input = sys.stdin.readline

def check(res, p):
	L = len(p)
	remain = L - res
	for i in range(res + 1):
		(l, r) = (p[i], p[i + remain - 1])
		if r - l + 1 - remain <= res:
			return True
	return False
T = int(input())
for _ in range(T):
	s = input()
	pos = []
	for i in range(len(s)):
		if s[i] == '1':
			pos.append(i)
	(l, r) = (int(0), len(pos))
	while r > l:
		mid = (l + r) // 2
		if check(mid, pos):
			r = mid
		else:
			l = mid + 1
	print(l)


def can(pos, m):
	k = len(pos)
	x = k - m
	for i in range(m + 1):
		l = pos[i]
		r = pos[i + x - 1]
		if r - l + 1 - x <= m:
			return True
	return False
t = int(input())
for i in range(t):
	s = input()
	pos = []
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			pos.append(i)
	lf = 0
	rg = len(pos)
	while rg - lf > 1:
		mid = (lf + rg) // 2
		if can(pos, mid):
			rg = mid
		else:
			lf = mid
	if len(pos) == 0 or pos[-1] - pos[0] == len(pos) - 1:
		print(0)
	else:
		print(rg)


def check(w, res):
	Len = len(w)
	cnt = Len - res
	for i in range(res + 1):
		(l, r) = (w[i], w[i + cnt - 1])
		if r - l + 1 - cnt <= res:
			return True
	return False
T = int(input())
for i in range(T):
	s = input()
	w = []
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			w.append(i)
	(l, r) = (0, len(w))
	while r > l:
		mid = (l + r) // 2
		if check(w, mid):
			r = mid
		else:
			l = mid + 1
	if len(w) == 0 or w[-1] - w[0] + 1 == len(w):
		print(0)
	else:
		print(l)


def main():
	s = input()
	(i1, i2) = (0, 1)
	(m1, m2) = (int(s[0] == '0'), s[1:].count('1'))
	min_ = 10 ** 9
	while True:
		min_ = min(min_, max(m1, m2))
		if m1 >= m2:
			i1 += 1
			if i1 == len(s) + 1:
				break
			if s[i1 - 1] == '0':
				m1 -= 1
			else:
				m2 += 1
		else:
			i2 += 1
			if i2 == len(s) + 1:
				break
			if s[i2 - 1] == '0':
				m1 += 1
			else:
				m2 -= 1
	min_ = min(min_, max(m1, m2))
	print(min_)
for i in range(int(input())):
	main()


def check(a, m):
	k = len(a)
	x = k - m
	for i in range(m + 1):
		l = a[i]
		r = a[i + x - 1]
		if r - l + 1 - x <= m:
			return True
	return False
t = int(input())
for i in range(t):
	s = input()
	a = []
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			a.append(i)
	l = 0
	r = len(a)
	while r - l > 1:
		mid = (l + r) // 2
		if check(a, mid):
			r = mid
		else:
			l = mid
	if len(a) == 0 or a[-1] - a[0] == len(a) - 1:
		print(0)
	else:
		print(r)


def check(pos, k):
	c = len(pos)
	x = c - k
	for i in range(k + 1):
		l = pos[i]
		r = pos[i + x - 1]
		if r - l + 1 - x <= k:
			return True
	return False
t = int(input())
for i in range(t):
	s = input()
	pos = []
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			pos.append(i)
	left = 0
	right = len(pos)
	while right - left > 1:
		mid = (left + right) // 2
		if check(pos, mid):
			right = mid
		else:
			left = mid
	if len(pos) == 0 or pos[-1] - pos[0] == len(pos) - 1:
		print(0)
	else:
		print(right)


def check(value):
	for onesleft in range(value + 1):
		zerosdeleted = left[onesleft] + right[value - onesleft]
		if zeros - zerosdeleted <= value:
			return True
	return False

def guess(mi, ma):
	if mi + 1 >= ma:
		if check(mi):
			return mi
		else:
			return mi + 1
	mid = (ma + mi) // 2
	if check(mid):
		return guess(mi, mid)
	else:
		return guess(mid, ma)
T = int(input())
for testcase in range(1, T + 1):
	s = input()
	zeros = s.count('0')
	n = len(s)
	ones = n - zeros
	if ones == 0:
		print(0)
	else:
		left = []
		count = 0
		for i in range(n):
			if s[i] == '1':
				left.append(count)
			else:
				count += 1
		right = []
		count = 0
		for i in range(n - 1, -1, -1):
			if s[i] == '1':
				right.append(count)
			else:
				count += 1
		print(guess(0, min(zeros, ones)))


import math
for _ in range(int(input())):
	bits = str(input())
	n = len(bits)
	n1 = 0
	n0 = 0
	for i in range(n):
		if int(bits[i]) == 1:
			n1 += 1
		else:
			n0 += 1
	(zin, oout) = (0, n1)
	j = 0
	ans = n1
	for i in range(n):
		while j < n and zin < oout:
			if int(bits[j]) == 0:
				zin += 1
			else:
				oout -= 1
			j += 1
		ans = min(ans, max(zin, oout))
		if int(bits[i]) == 0:
			zin -= 1
		else:
			oout += 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	zb = [0]
	ze = [0]
	ob = [0]
	oe = [0]
	c = 0
	for j in s:
		if j == '0':
			c += 1
		zb.append(c)
	z = zb[-1]
	c = 0
	for j in s:
		if j == '1':
			c += 1
		ob.append(c)
	o = ob[-1]
	c = 0
	for j in range(len(s)):
		if s[-j - 1] == '0':
			c += 1
		ze.append(c)
	c = 0
	for j in range(len(s)):
		if s[-j - 1] == '1':
			c += 1
		oe.append(c)
	ans = 999999999
	for j in range(len(s)):
		cost0 = z - zb[j] - ze[z - zb[j]]
		cost1 = ob[j] + oe[z - zb[j] - ob[j]]
		ans = min(max(cost0, cost1), ans)
	print(ans)


mi = lambda : map(int, input().split())

def check(pre, mid, pos):
	rem = len(pos) - mid
	for i in range(len(pos) + 1 - rem):
		l = pos[i]
		r = pos[i + rem - 1]
		if r - l + 1 - (pre[r + 1] - pre[l]) <= mid:
			return True
	return False
for t in range(int(input())):
	s = str(input())
	if '1' not in s:
		print(0)
		continue
	pre = [0]
	pos = []
	for i in range(len(s)):
		if s[i] == '1':
			pos.append(i)
		pre.append(pre[-1] + int(s[i]))
	l = 0
	r = s.count('1')
	while r - l > 1:
		mid = (r + l) // 2
		if not check(pre, mid, pos):
			l = mid
		else:
			r = mid
	if check(pre, l, pos):
		print(l)
	else:
		print(r)


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	zero = 0
	one = 0
	for i in range(n):
		if s[i] == '0':
			zero += 1
		else:
			one += 1
	r = -1
	l = -1
	r0 = zero
	r1 = one
	l0 = 0
	l1 = 0
	ans = n + 2
	while r < n:
		ans = min(ans, max(zero - (r0 + l0), r1 + l1))
		r += 1
		if r < n:
			if s[r] == '0':
				r0 -= 1
			else:
				r1 -= 1
		ans = min(ans, max(zero - (r0 + l0), r1 + l1))
		while l < r and l < n:
			if zero - (r0 + l0) - (r1 + l1) <= 0:
				break
			ans = min(ans, max(zero - (r0 + l0), r1 + l1))
			l += 1
			if l < r and l < n:
				if s[l] == '0':
					l0 += 1
				else:
					l1 += 1
			ans = min(ans, max(zero - (r0 + l0), r1 + l1))
	ans = min(ans, max(zero - (r0 + l0), r1 + l1))
	print(ans)
	t -= 1


t = int(input())
for ts in range(t):
	s = input()
	pos = []
	for i in range(len(s)):
		if s[i] == '0':
			pos.append(i)
	sm = [0]
	for i in s:
		sm.append(sm[-1] + (1 if i == '1' else 0))
	l = -1
	r = len(pos)
	while l + 1 != r:
		mid = (l + r) // 2
		ok = False
		for i in range(len(pos) - mid + 1):
			if i == 0:
				ll = 0
			else:
				ll = pos[i - 1] + 1
			if i == len(pos) - mid:
				rr = len(s) - 1
			else:
				rr = pos[i + mid] - 1
			if sm[ll] + sm[-1] - sm[rr + 1] <= mid:
				ok = True
				break
		if ok:
			r = mid
		else:
			l = mid
	print(r)


def binsearch(l, r, check):
	while l + 1 < r:
		m = (l + r) // 2
		if check(m):
			r = m
		else:
			l = m
	return (l, r)

def work():
	s = input()
	sv = [int(c) for c in s]
	totalonecount = sum(sv)
	n = len(s)

	def check(cost):
		start = 0
		width = 0
		curcount = [0, 0]
		while True:
			if curcount[0] <= cost:
				if curcount[1] < totalonecount - cost:
					if start + width == n:
						return False
					newhire = sv[start + width]
					width += 1
					curcount[newhire] += 1
				else:
					return True
			else:
				victim = sv[start]
				start += 1
				width -= 1
				curcount[victim] -= 1
	(l1, r1) = binsearch(-1, n, check)
	return r1
tn = int(input())
for ti in range(tn):
	print(work())