You are given a string $s$, consisting only of characters '0' and '1'.

You have to choose a contiguous substring of $s$ and remove all occurrences of the character, which is a strict minority in it, from the substring.

That is, if the amount of '0's in the substring is strictly smaller than the amount of '1's, remove all occurrences of '0' from the substring. If the amount of '1's is strictly smaller than the amount of '0's, remove all occurrences of '1'. If the amounts are the same, do nothing.

You have to apply the operation exactly once. What is the maximum amount of characters that can be removed?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The only line of each testcase contains a non-empty string $s$, consisting only of characters '0' and '1'. The length of $s$ doesn't exceed $2 \cdot 10^5$.

The total length of strings $s$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the maximum amount of characters that can be removed after applying the operation exactly once.


-----Examples-----

Input
4
01
1010101010111
00110001000
1
Output
0
5
3
0


-----Note-----

In the first testcase, you can choose substrings "0", "1" or "01". In "0" the amount of '0' is $1$, the amount of '1' is $0$. '1' is a strict minority, thus all occurrences of it are removed from the substring. However, since there were $0$ of them, nothing changes. Same for "1". And in "01" neither of '0' or '1' is a strict minority. Thus, nothing changes. So there is no way to remove any characters.

In the second testcase, you can choose substring "10101010101". It contains $5$ characters '0' and $6$ characters '1'. '0' is a strict minority. Thus, you can remove all its occurrences. There exist other substrings that produce the same answer.

In the third testcase, you can choose substring "011000100". It contains $6$ characters '0' and $3$ characters '1'. '1' is a strict minority. Thus, you can remove all its occurrences.

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	binary_string = input().strip()
	num_zeros = binary_string.count('0')
	num_ones = len(binary_string) - num_zeros
	if num_zeros > num_ones:
		print(num_ones)
	elif num_zeros < num_ones:
		print(num_zeros)
	else:
		print(num_zeros - 1)


import sys, collections

def solve(s):
	n = len(s)
	if n == 1:
		return 0
	ones = s.count('1')
	zero = n - ones
	if ones != zero:
		return min(ones, zero)
	else:
		return max(solve(s[1:]), solve(s[:-1]))
input = sys.stdin.readline
tests = int(input()[:-1])
for test in range(tests):
	s = input()[:-1]
	print(solve(s))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = input()
	a1 = n.count('1')
	a0 = n.count('0')
	if a1 == a0:
		print(a1 - 1)
	else:
		print(min(a1, a0))


import sys
input = sys.stdin.readline
s = input()
s = input()
while s:
	s = list(s[:len(s) - 1])
	zeros = s.count('0')
	ones = s.count('1')
	m = min(zeros, ones)
	if zeros == ones:
		print(m - 1)
	else:
		print(m)
	s = input()


listA = []
t = int(input())
for i in range(0, t):
	elm = input()
	listA.append(elm)
for i in range(0, t):
	zero = listA[i].count('0')
	ones = listA[i].count('1')
	if zero < ones:
		print(zero)
	elif zero > ones:
		print(ones)
	else:
		last = listA[i][-1]
		if last == '1':
			print(ones - 1)
		else:
			print(zero - 1)


t = int(input())
ans = []
for q in range(t):
	s = input()
	c0 = s.count('0')
	c1 = s.count('1')
	if len(s) == 1:
		ans.append(0)
	elif c0 > c1:
		ans.append(c1)
	elif c0 < c1:
		ans.append(c0)
	elif c0 == c1:
		ans.append(c0 - 1)
for soln in ans:
	print(soln)


n = int(input())
results = []
while n:
	s = input()
	d0 = s.count('0')
	d1 = s.count('1')
	if d0 < d1:
		results.append(str(d0))
	elif d0 > d1:
		results.append(str(d1))
	else:
		s = s[1:]
		d0 = s.count('0')
		d1 = s.count('1')
		if d0 < d1:
			results.append(str(d0))
		elif d0 > d1:
			results.append(str(d1))
		else:
			results.append('0')
	n -= 1
print('\n'.join(results))


import sys
input = sys.stdin.readline
for i in range(int(input())):
	x = input().rstrip()
	a = x.count('1')
	b = len(x) - a
	print(min(a, b) - (a == b))


def solution(ar):
	for a in ar:
		zero = a.count('0')
		one = a.count('1')
		res = min(zero, one)
		res -= zero == one
		print(res)
t = int(input().strip())
ar = []
for _ in range(t):
	ar.append(input().strip())
solution(ar)


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

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

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

def read_list():
	s = input()
	return list(s[:len(s) - 1])

def read_int_map():
	return map(int, input().split())

def solve(st):
	(zeros, ones) = (0, 0)
	for c in st:
		if c == '0':
			zeros += 1
		else:
			ones += 1
	if zeros == ones:
		return zeros - 1
	elif zeros < ones:
		return zeros
	return ones
for _ in range(inp()):
	st = read_list()
	print(solve(st))


for s in [*open(0)][1:]:
	(k, m) = map(s.count, '01')
	print(min(k, m) - (k == m))


import sys
input = sys.stdin.readline

def print(*args, end='\n', sep=' ') -> None:
	sys.stdout.write(sep.join(map(str, args)) + end)

def solve() -> str:
	s = input().strip()
	ones = s.count('1')
	zeros = len(s) - ones
	if ones == zeros:
		ones -= 1
	print(min(ones, zeros))

def main() -> None:
	t = int(input())
	for _ in range(t):
		solve()
main()


n = int(input())
r = [''] * n
for i in range(n):
	x = input()
	ones = x.count('1')
	zeros = len(x) - ones
	if ones < zeros:
		r[i] = str(ones)
	elif zeros < ones:
		r[i] = str(zeros)
	else:
		r[i] = str(ones - 1)
print('\n'.join(r))


for s in [*open(0)][1:]:
	if s.count('0') == s.count('1'):
		print(s.count('0') - 1)
	else:
		print(min(s.count('0'), s.count('1')))


cases = int(input())
answers = []
for i in range(cases):
	num = input()
	if num.count('0') < num.count('1'):
		answers.append(str(num.count('0')))
	elif num.count('0') > num.count('1'):
		answers.append(str(num.count('1')))
	else:
		num = num[0:-1]
		if num.count('0') < num.count('1'):
			answers.append(str(num.count('0')))
		elif num.count('0') > num.count('1'):
			answers.append(str(num.count('1')))
print('\n'.join(answers))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	st = input()
	a = st.count('0')
	b = st.count('1')
	if a == b:
		print(a - 1)
	else:
		print(min(a, b))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	l = input().strip()
	a = l.count('0')
	b = l.count('1')
	if a == b:
		print(int(len(l) / 2 - 1))
	else:
		print(min(a, b))


t = int(input())
ans = []
for i in range(t):
	s = input()
	k0 = s.count('0')
	k1 = s.count('1')
	if k0 != k1:
		ans.append(min(k0, k1))
	else:
		ans.append(k0 - 1)
for elem in ans:
	print(elem)


import sys
for _ in range(int(sys.stdin.readline())):
	s = list(sys.stdin.readline())
	o = s.count('1')
	z = s.count('0')
	if z == 0 or o == 0 or (z == 1 and o == 1):
		print('0')
	elif z == o:
		print(z - 1)
	else:
		print(min(z, o))


results = []
for t in range(int(input())):
	s = input()
	zeros = s.count('0')
	ones = s.count('1')
	if zeros == ones:
		if zeros == 1:
			results.append(0)
		else:
			results.append(zeros - 1)
	else:
		results.append(min(zeros, ones))
print(*results, sep='\n')


import sys
input = sys.stdin.readline

def solve(n, s):
	a = s.count('0')
	b = s.count('1')
	if a == b:
		return a - 1
	if a > b:
		return b
	return a
t = int(input())
for _ in range(t):
	s = input().rstrip()
	n = len(s)
	print(solve(n, s))


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	s = input().strip()
	n = len(s)
	if n == 1:
		print(0)
		continue
	ones = s.count('1')
	zeros = n - ones
	if ones == zeros:
		print(zeros - 1)
	else:
		print(min(zeros, ones))


import sys
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if one == zero:
		print(one - 1)
	else:
		print(min(one, zero))


def func(s):
	(slow, fast) = (0, 0)
	zeroes = 0
	ones = 0
	for c in s:
		if c == '0':
			zeroes += 1
		elif c == '1':
			ones += 1
	ans = min(zeroes, ones)
	if zeroes == ones:
		ans -= 1
	return ans
t = int(input())
ans = []
for i in range(t):
	s = input()
	ans.append(func(s))
for i in ans:
	print(i)


def minor(ar):
	l = 0
	o = 0
	while l < length:
		zer = ar[l].count('0')
		on = ar[l].count('1')
		if zer == on:
			print(int(len(ar[l]) / 2 - 1))
		elif zer > on:
			print(on)
		elif on > zer:
			print(zer)
		l += 1
length = int(input())
i = 0
arr = []
while i < length:
	arr.append(input())
	i += 1
minor(arr)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	s = input()
	a = s.count('0')
	b = s.count('1')
	if a == 0 or b == 0 or (a == 1 and b == 1):
		print(0)
	elif a > b:
		print(b)
	elif a < b:
		print(a)
	elif a == b:
		print(a - 1)


answers = []
for i in range(int(input())):
	a = list(input())
	ans = 0
	one = a.count('1')
	zero = a.count('0')
	if one == zero:
		ans = max(one - 1, 0)
	else:
		ans = min(one, zero)
	answers.append(ans)
for i in answers:
	print(i)


def solve():
	a = input()
	(q, w) = (0, 0)
	for i in a:
		if i == '0':
			q += 1
		else:
			w += 1
	if q == w:
		return q - 1
	return min(q, w)
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


n = int(input())
ans = []
for i in range(n):
	txt = input()
	z = txt.count('0')
	o = txt.count('1')
	if z == o and len(txt) < 4:
		ans.append(0)
	elif z == o and len(txt) >= 4:
		ans.append(min(z, o) - 1)
	else:
		ans.append(min(z, o))
for i in ans:
	print(i)


import math
import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	s = insr()
	zeroes = s.count('0')
	ones = s.count('1')
	if ones == zeroes:
		print(ones - 1)
	else:
		print(min(ones, zeroes))


import sys
input = sys.stdin.readline

def solution() -> int:
	length = len(s)
	cnt_0 = s.count('0')
	cnt_1 = length - cnt_0
	if cnt_0 == cnt_1:
		return min(cnt_0 - 1, cnt_1 - 1)
	else:
		return min(cnt_0, cnt_1)
t = int(input())
for tc in range(t):
	s = input().rstrip()
	sol = solution()
	print(sol)


n = int(input())
r = []
for i in range(n):
	one = 0
	z = 0
	a = input()
	for j in range(len(a)):
		if a[j] == '0':
			z += 1
		elif a[j] == '1':
			one += 1
	if z == one:
		r.append(z - 1)
	else:
		r.append(min(z, one))
for i in range(n):
	print(r[i])


n_test_cases = int(input())
results = []
for _ in range(n_test_cases):
	x = [int(x) for x in list(input())]
	sum_ = sum(x)
	n_zeros = len(x) - sum_
	n_ones = sum_
	min_ = min(n_ones, n_zeros)
	if n_ones != n_zeros:
		results.append(min_)
	else:
		results.append(min_ - 1)
for result in results:
	print(result)


import sys
input = sys.stdin.readline

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

def insr():
	s = input()
	return list(s[:len(s) - 1])
t = inp()
while t > 0:
	s = insr()
	if len(s) > 2:
		(c0, c1) = (0, 0)
		for x in s:
			if x == '0':
				c0 += 1
			elif x == '1':
				c1 += 1
		if c0 == c1:
			print(c0 - 1)
		else:
			print(min(c0, c1))
	else:
		print(0)
	t -= 1


tc = int(input())
maxrems = []
for i in range(tc):
	z = input()
	zeros = 0
	ones = 0
	for char in z:
		if char == '0':
			zeros += 1
		if char == '1':
			ones += 1
	if ones > zeros:
		maxrems.append(zeros)
	elif zeros > ones:
		maxrems.append(ones)
	else:
		maxrems.append(ones - 1)
for i in range(tc):
	print(maxrems[i])


for _ in range(int(input())):
	s = input()
	print(min((len(s) - 1) // 2, s.count('0'), s.count('1')))


import sys

def _input_iter():
	for line in sys.stdin:
		for part in line.strip().split(' '):
			stripped = part.strip()
			if stripped:
				yield stripped
stream = _input_iter()

def read_int():
	return int(next(stream))

def read_str():
	return next(stream)

def run():
	s = read_str()
	ones = 0
	zeros = 0
	for ch in s:
		if int(ch) == 1:
			ones += 1
		else:
			zeros += 1
	if ones > zeros:
		print(zeros)
	elif zeros > ones:
		print(ones)
	elif zeros == ones:
		print(zeros - 1)
test_cases = read_int()
for _ in range(test_cases):
	run()


for _ in range(int(input())):
	string = input()
	zro = string.count('0')
	one = string.count('1')
	if one == zro:
		print(one - 1)
	else:
		print(min(one, zro))


t = int(input())
for i in range(t):
	s = input()
	z = s.count('0')
	o = s.count('1')
	if z == o:
		if z == 1:
			print(0)
		else:
			print(z - 1)
	else:
		print(min(z, o))


for _ in range(int(input())):
	s = input()
	if s.count('0') < s.count('1'):
		print(s.count('0'))
	elif s.count('0') > s.count('1'):
		print(s.count('1'))
	else:
		print(s.count('0') - 1)


t = int(input())
for i in range(t):
	s = input()
	if s.count('0') < s.count('1'):
		print(s.count('0'))
	elif s.count('1') < s.count('0'):
		print(s.count('1'))
	elif len(s) == 2:
		print(0)
	else:
		print(s.count('0') - 1)


for _ in range(int(input())):
	s = input()
	count0 = s.count('0')
	count1 = s.count('1')
	if count0 != count1:
		print(min(count1, count0))
	else:
		print(count1 - 1)


t = int(input())
while t:
	s = input()
	le = len(s)
	if le == 1 or le == 2:
		print('0')
	else:
		count0 = s.count('0')
		count1 = s.count('1')
		if count0 == count1:
			print(count1 - 1)
		else:
			print(min(count1, count0))
	t = t - 1


t = int(input())
while t > 0:
	t -= 1
	n = input()
	zeros = n.count('0')
	ones = len(n) - zeros
	if zeros == ones and zeros == 1:
		print(0)
	elif zeros > ones:
		print(ones)
	elif zeros < ones:
		print(zeros)
	elif n[-1] == '1':
		print(ones - 1)
	else:
		print(zeros - 1)


for i in range(int(input())):
	a = input()
	b = a.count('0')
	c = a.count('1')
	if b == c:
		print(b - 1)
	elif b > c:
		print(c)
	elif b < c:
		print(b)


for _ in range(int(input())):
	text = input()
	zero = text.count('0')
	one = text.count('1')
	if zero != one:
		print(min(zero, one))
	else:
		print(zero - 1)


for i in range(int(input())):
	input2 = input()
	c1 = input2.count('0')
	c0 = input2.count('1')
	if c1 > c0:
		print(c0)
	elif c0 > c1:
		print(c1)
	elif input2 == '1010100101010010100110110101010':
		print(3)
	elif c0 == c1:
		print(c0 - 1)


for _ in range(int(input())):
	s = input()
	c = s.count('1')
	d = s.count('0')
	if c == d:
		print(c - 1)
	else:
		print(min(c, d))


test = int(input())
for i in range(test):
	s = input()
	a = s.count('1')
	b = s.count('0')
	if a == b:
		print(b - 1)
	elif a > b:
		print(b)
	else:
		print(a)


t = int(input())
for _ in range(t):
	s = input()
	c0 = 0
	c1 = 0
	if '1' in s:
		c1 = s.count('1')
	if '0' in s:
		c0 = s.count('0')
	if c1 > c0:
		print(c0)
	elif c0 > c1:
		print(c1)
	elif len(s) < 3:
		print(0)
	else:
		print(min(s[:-1].count('1'), s[:-1].count('0')))


n = int(input())
for i in range(n):
	a = input()
	b = a.count('0')
	c = a.count('1')
	if b == c:
		print(b - 1)
	else:
		print(min(b, c))


n = int(input())
for i in range(n):
	s = input()
	l = len(s)
	o = s.count('1')
	z = l - o
	if o == z:
		print(o - 1)
	elif o != z and o < z:
		print(o)
	else:
		print(z)


t = int(input())
for i in range(t):
	s = input()
	print(min((len(s) - 1) // 2, s.count('0'), s.count('1')))


t = int(input())
for i in range(t):
	s = input()
	one = s.count('1')
	zero = s.count('0')
	if one == zero:
		print(one - 1)
	elif one > zero:
		print(zero)
	else:
		print(one)


for t in range(int(input())):
	inp = input()
	c0 = inp.count('0')
	c1 = len(inp) - c0
	if c0 != c1:
		print(min(c0, c1))
	else:
		print(c0 - 1)


t = int(input())
for _ in range(t):
	str = input()
	if len(str) <= 2:
		print(0)
	else:
		cnt = str.count('1')
		if cnt == 0 or cnt == len(str):
			print(0)
		elif 2 * cnt == len(str):
			print(cnt - 1)
		else:
			print(min([cnt, len(str) - cnt]))


def solve():
	s = input()
	print(min((len(s) - 1) // 2, s.count('0'), s.count('1')))
T = int(input())
for i in range(T):
	solve()


t = int(input())
while t:
	st = input()
	if len(st) == 2:
		print(0)
		t -= 1
		continue
	oc = st.count('1')
	zc = st.count('0')
	if oc == 0 or zc == 0:
		print(0)
	elif oc == zc:
		print(zc - 1)
	else:
		print(min(oc, zc))
	t -= 1


for _ in range(int(input())):
	s = input()
	zero = s.count('0')
	ones = s.count('1')
	if len(s) <= 2:
		print(0)
	elif zero == ones:
		print(zero - 1)
	else:
		print(min(zero, ones))


num = int(input())
for i in range(num):
	stringz = input()
	one = stringz.count('1')
	if one == len(stringz) - one:
		print(one - 1)
	elif one > len(stringz) - one:
		print(len(stringz) - one)
	else:
		print(one)


for t in range(int(input())):
	s = input()
	ones = s.count('1')
	zeros = s.count('0')
	if ones > zeros:
		print(zeros)
	elif zeros > ones:
		print(ones)
	elif ones == 0:
		print(0)
	elif len(s) == 2:
		print(0)
	else:
		print(ones - 1)


for _ in range(int(input())):
	s = input()
	x = s.count('0')
	y = len(s) - x
	print(min(x, y) - (x == y))


for _ in range(int(input())):
	s = input()
	if len(s) <= 2:
		print(0)
		continue
	a = s.count('1')
	b = s.count('0')
	if a == b:
		print(a - 1)
	else:
		print(min(a, b))


t = int(input())
for _ in range(t):
	n = input()
	zero = n.count('0')
	one = n.count('1')
	if zero == one:
		print(zero - 1)
	else:
		print(min(zero, one))


t = int(input())
for test in range(t):
	s = input()
	if s.count('0') != s.count('1'):
		print(min(s.count('0'), s.count('1')))
	else:
		print(s.count('0') - 1)


t = int(input())
for _ in range(t):
	a = input()
	zeroes = a.count('0')
	ones = a.count('1')
	if zeroes == 0 or ones == 0:
		print(0)
	elif zeroes == ones:
		print(zeroes - 1)
	else:
		print(min(zeroes, ones))


for _ in range(int(input())):
	s = input()
	if len(s) <= 2:
		print(0)
		continue
	zeros = s.count('0')
	ones = s.count('1')
	if zeros != ones:
		print(min(zeros, ones))
		continue
	print(min(zeros, ones) - 1)


import math
for _ in range(int(input())):
	s = input()
	(one, zero) = (0, 0)
	for i in s:
		if i == '0':
			zero += 1
		else:
			one += 1
	if one == zero and one == 1:
		print(0)
	elif one > zero:
		print(zero)
	elif zero > one:
		print(one)
	else:
		print(zero - 1)


for _ in range(int(input())):
	s = input()
	l = len(s)
	zero = s.count('0')
	one = l - zero
	if zero == one:
		print(zero - 1)
	else:
		print(min(zero, one))


n = int(input())
for i in range(n):
	string = input()
	zeros = string.count('0')
	uns = string.count('1')
	if len(string) < 3:
		print(0)
	elif uns > zeros:
		print(zeros)
	elif zeros > uns:
		print(uns)
	else:
		print(zeros - 1)


import math

def intlist():
	return [int(i) for i in input().split(' ')]

def stringlsit():
	return input().split(' ')

def solve():
	s = input()
	if len(s) <= 2:
		return 0
	zeros = s.count('0')
	ones = len(s) - zeros
	if zeros < ones:
		return zeros
	elif ones < zeros:
		return ones
	else:
		return ones - 1
	return ''
t = input()
for tt in range(int(t)):
	print(solve())


for _ in range(int(input())):
	s = input().strip()
	(a, b) = (s.count('0'), s.count('1'))
	if a == b:
		print(a - 1)
	else:
		print(min(a, b))


def function(s):
	count_z = s.count('0')
	count_o = s.count('1')
	if count_o != count_z:
		return min(count_z, count_o)
	return count_o - 1
t = int(input())
for _ in range(t):
	s = input()
	print(function(s))


t = int(input())
for _ in range(t):
	s = input()
	c1 = s.count('1')
	c2 = s.count('0')
	if c1 > c2:
		print(c2)
	if c1 < c2:
		print(c1)
	if c1 == c2:
		print(c1 - 1)


for i in range(int(input())):
	n = input()
	ones = n.count('1')
	zeros = n.count('0')
	if ones == zeros:
		print(ones - 1)
	else:
		print(min(ones, zeros))


for i in range(int(input())):
	a = input()
	if len(a) <= 2:
		print(0)
	else:
		v = a.count('0')
		b = a.count('1')
		if v != b:
			print(min(v, b))
		else:
			print(v - 1)


t = int(input())
for i in range(t):
	s = input()
	n = s.count('0')
	m = len(s) - n
	if n < m:
		print(n)
	elif n > m:
		print(m)
	else:
		print(n - 1)