Chef has a binary string S with him and he wants to modify it using the following two types of operations - 

Type 1 : Choose any two indices i and j such that 1 ≤ i, j ≤ |S| and swap S_{i} and S_{j}. This operation costs 1 rupee and can be performed any number of times.
Type 2 :  Choose any prefix of length i, where 1 ≤ i ≤ |S|, and reverse this prefix of the binary string. This operation is free of cost and can be performed at most once.

Chef wants to obtain the lexicographically smallest string. Can you help him find the minimum cost to obtain the lexicographically smallest string?

Note:
|S| denotes the length of the string S.
A string A is lexicographically smaller than string B, if A_{i} < B_{i}, where i is the first index where A and B differ.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line of input denoting S, the original string.

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

For each test case, output the minimum cost to obtain the lexicographically minimal string.

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

$1 ≤ T ≤ 5\cdot 10^{4}$
$1 ≤ |S| ≤ 10^{5}$
- The sum of $|S|$ over all test cases won't exceed $5\cdot 10^{5}$.

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

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
3
1010
101
100100

----- Sample Output 1 ------ 
1
0
1

----- explanation 1 ------ 
Test case 1: You can perform an operation of Type 1 by choosing $i = 2$ and $j = 3$. So from $1\textcolor{violet}{0}\textcolor{olive}{1}0$, you get $1100$, and it has cost you $1$ rupee so far. Then, you perform an operation of Type 2, by choosing $i = 4$. So you reverse the entire string, and so from $\textcolor{red}{1100}$, you get $0011$. This operation is free of cost. This is the lexicographically smallest string that you can achieve, and it cost us $1$ rupee to get there. So the answer is $1$.

Test case 2: You can perform an operation of Type 2, by choosing $i = 2$. So you reverse the prefix of length 2, and so from $\textcolor{red}{10}1$, you get $011$. This operation is free of cost. This is the lexicographically smallest string that you can achieve, and it cost us $0$ rupees to get there. So the answer is $0$.

Test case 3: You can perform an operation of Type 1 by choosing $i = 4$ and $j = 6$. So from $100\textcolor{violet}{1}0\textcolor{olive}{0}$, you get $100001$, and it has cost you $1$ rupee so far. Then, you perform an operation of Type 2, by choosing $i = 5$. So you reverse the prefix of length 5, and so from $\textcolor{red}{10000}1$, you get $000011$. This operation is free of cost. This is the lexicographically smallest string that you can achieve, and it cost us $1$ rupee to get there. So the answer is $1$.

Difficulty: HARD
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	s = input()
	cnt = 0
	ncnt = 0
	for i in range(len(s)):
		cnt += s[i] == '0'
	if not cnt:
		print('0')
		continue
	for i in range(cnt):
		ncnt += s[i] == '0'
	ans = cnt - ncnt
	for i in range(cnt, len(s)):
		ncnt -= s[i - cnt] == '0'
		ncnt += s[i] == '0'
		ans = min(ans, cnt - ncnt)
	print(ans)


t = int(input())
for _ in range(t):
	b = list(map(int, input().strip()))
	z = len(b) - sum(b)
	if z == 0:
		print(0)
		continue
	a = b[0:z]
	s = sum(a)
	maxim = s
	for i in range(z, len(b)):
		if a[0] == 1:
			s -= 1
		if b[i] == 1:
			s += 1
		a.pop(0)
		a.append(b[i])
		if s < maxim:
			maxim = s
	print(maxim)


T = int(input())
for _ in range(T):
	bs = input()
	(x, y) = (0, 0)
	for i in bs:
		if i == '0':
			x += 1
		if i == '1':
			y += 1
	a = bs[:x].count('0')
	c = a
	for i in range(x, len(bs)):
		if bs[i] == '0':
			c += 1
		if bs[i - x] == '0':
			c -= 1
		a = max(a, c)
	print(x - a)


for i in range(int(input())):
	s = input()
	m = s.count('0')
	count = s[:m].count('1')
	mincount = count
	lowlim = 0
	uplim = m
	while uplim < len(s):
		if s[uplim] == '1':
			count += 1
		if s[lowlim] == '1':
			count -= 1
		lowlim += 1
		uplim += 1
		if count < mincount:
			mincount = count
	print(mincount)


for _ in range(int(input())):
	s = input()
	x = s.count('0')
	m = len(s)
	a = s[0:x].count('0')
	b = a
	for i in range(x, m):
		if s[i] == '0' and s[i - x] == '1':
			b += 1
		elif s[i] == '1' and s[i - x] == '0':
			b -= 1
		if b > a:
			a = b
	print(x - a)


def func1():
	s = list(input())
	ct = 0
	nct = 0
	for i in range(len(s)):
		if s[i] == '0':
			ct += 1
	if ct == 0:
		print('0')
		return
	for j in range(ct):
		if s[j] == '0':
			nct += 1
	one_ct = ct - nct
	for k in range(ct, len(s)):
		if s[k - ct] == '0':
			nct -= 1
		if s[k] == '0':
			nct += 1
		one_ct = min(one_ct, ct - nct)
	print(one_ct)
for t in range(int(input())):
	func1()


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


for _ in range(int(input())):
	string = input()
	s = list(map(int, string))
	k = string.count('0')
	pref = [0]
	for ele in s:
		pref.append(pref[-1] + ele)
	ans = float('inf')
	for i in range(len(s) - k + 1):
		cost = pref[i + k] - pref[i]
		ans = min(ans, cost)
	print(ans)


for _ in range(int(input())):
	s = input()
	k = s.count('0')
	if k == len(s):
		print(0)
		continue
	m = s[:k].count('0')
	ans = k - m
	for i in range(k, len(s)):
		m -= s[i - k] == '0'
		m += s[i] == '0'
		ans = min(ans, k - m)
	print(ans)


for _ in range(int(input())):
	B = list(input())
	N = len(B)
	K = B.count('0')
	mnOnes = float('inf')
	ones = 0
	for i in range(N - K + 1):
		if i == 0:
			ones = B[i:K + i].count('1')
		else:
			ones = ones - (1 if B[i - 1] == '1' else 0) + (1 if K + i - 1 < N and B[K + i - 1] == '1' else 0)
		if mnOnes > ones:
			mnOnes = ones
	print(mnOnes)


T = int(input())
for _ in range(T):
	arr = list(map(int, list(input())))
	n = len(arr)
	num1s = arr.count(1)
	orig_num1s = num1s - arr[::-1][:num1s].count(1)
	best_transpose = 0
	ones_corrected = 0
	best_i = 0
	for i in range(num1s):
		if arr[i] == 1:
			ones_corrected += 1
		if arr[i + n - num1s] == 1:
			ones_corrected -= 1
		if ones_corrected >= best_transpose:
			best_transpose = ones_corrected
			best_i = i
	best_arr = arr[best_i + n - num1s + 1:][::-1] + arr[:best_i + n - num1s + 1]
	fin_num1s = num1s - best_arr[:num1s].count(1)
	print(min(orig_num1s, fin_num1s))


import sys
a = [None] * 100001
b = [0] * 100001

def query(l, r):
	return b[r] - b[l - 1]

def sol():
	st = input()
	n = len(st)
	s = 99999
	for i in range(n):
		a[i + 1] = ord(st[i]) - 48
	for i in range(1, n + 1):
		b[i] = b[i - 1] + a[i]
	m = query(1, n)
	for i in range(1, n + 1):
		if n - i - query(i + 1, n) > query(1, i):
			continue
		s = min(s, n - i - query(i + 1, n) + query(1, i) - (n - i - query(i + 1, n)) - query(1, query(1, i) - (n - i - query(i + 1, n))))
	print(s)
T = int(input())
for i in range(T):
	sol()


test = int(input())
for t in range(test):
	s = input()
	a = [0] * (len(s) + 1)
	out = float('inf')
	for i in range(len(s)):
		a[i + 1] = int(s[i])
	n = len(s)
	b = [0] * (n + 1)
	for i in range(1, n + 1):
		b[i] = b[i - 1] + a[i]
	m = b[n] - b[0]
	for i in range(1, n + 1):
		if n - i - (b[n] - b[i]) > b[i] - b[0]:
			continue
		x = b[i] - b[0] - (n - i - (b[n] - b[i]))
		out = min(out, n - i - (b[n] - b[i]) + (b[i] - b[0]) - (n - i - (b[n] - b[i])) - (b[x] - b[0]))
	print(out)


def ques(a, b, B):
	return B[b] - B[a - 1]
T = int(input())
for _ in range(T):
	A = [s for s in input()]
	B = [0] * (len(A) + 2)
	C = [0] * len(B)
	for i in range(len(A)):
		B[i + 1] = ord(A[i]) - 48
	N = len(A)
	s = 2147483647
	for i in range(1, N + 1):
		C[i] = C[i - 1] + B[i]
	M = ques(1, N, C)
	for i in range(1, N + 1):
		if N - i - ques(i + 1, N, C) > ques(1, i, C):
			continue
		s = min(s, N - i - ques(i + 1, N, C) + ques(1, i, C) - (N - i - ques(i + 1, N, C)) - ques(1, ques(1, i, C) - (N - i - ques(i + 1, N, C)), C))
	print(s)


for _ in range(int(input())):
	s = [int(x) for x in list(input())]
	n = len(s)
	sm = sum(s)
	if sm == 0:
		print(0)
		continue
	sm1 = [0 for i in range(sm)]
	sm2 = [0 for i in range(sm)]
	sm1[0] = s[0]
	sm2[0] = s[-1]
	for i in range(1, sm):
		sm1[i] = sm1[i - 1] + s[i]
		sm2[i] = sm2[i - 1] + s[-i - 1]
	mn = max(sm1[sm - 1], sm2[sm - 1])
	for i in range(0, sm - 1):
		mn = max(mn, sm1[i] + sm2[sm - i - 2])
	print(sm - mn)


T = int(input())
for _ in range(T):
	S = list(map(int, list(input())))
	zeroes = S.count(0)
	pref = [0]
	for elt in S:
		pref.append(pref[-1] + elt)

	def somme(a, b):
		return pref[b] - pref[a]
	ans = float('inf')
	for i in range(len(S) - zeroes + 1):
		cost = somme(i, i + zeroes)
		ans = min(ans, cost)
	print(ans)