You are given a binary string S. A binary string is a string consisting of only 0's and 1's.

A binary string is called *good* if it has an equal number of occurrences of \texttt{01} substrings and \texttt{10} substrings. Note that these substrings may overlap. For example, the string 1101001 is *good* since there are two occurrences of \texttt{01} (11\underline{01}001 and 11010\underline{01}) and two occurrences of \texttt{10} (1\underline{10}1001 and 110\underline{10}01).

Find the number of indices i (1 ≤ i ≤ |S|) such that after flipping S_{i}, the resultant binary string is *good*. (If S_{i} is 0, flipping it changes it to 1, and if S_{i} is 1, flipping it changes it to 0)

Note: A string A is a substring of a string B if A can be obtained from B by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The second line of each test case contains a binary string S containing 0s and 1s only.

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

For each test case, output on a single line the number indices i such that flipping S_{i} results in a *good* binary string.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ |S| ≤ 2\cdot10^{5}$
- The sum of lengths of $S$ over all test cases does not exceed $2\cdot10^{5}$.

----- Sample Input 1 ------ 
2
10100
11111
----- Sample Output 1 ------ 
2
3
----- explanation 1 ------ 
Test case 1: When $i = 1$, flipping $S_{1}$ produces the string $00100$, which is *good* since there is one occurrence of $\texttt{01}$ ($0\underline{01}00$) and one occurrence of $\texttt{10}$ ($00\underline{10}0$).

When $i = 5$, flipping $S_{5}$ produces the string $10101$, which is *good* since there are two occurrences of $\texttt{01}$ ($1\underline{01}01$ and $101\underline{01}$) and are two occurrences of $\texttt{10}$ ($\underline{10}101$ and $10\underline{10}1$).

It can be shown that for $i = 2, 3, 4$ flipping $S_{i}$ does not result in a *good* binary string.

Thus the number of indices resulting in a good binary string is $2$.

Difficulty: MEDIUM
Tags: String algorithms

Starter code:

Solutions:
tc = int(input())
for t in range(tc):
	b = input()
	if b[0] == b[-1]:
		print(len(b) - 2)
	else:
		print(2)


t = int(input())
while t:
	t -= 1
	s = input()
	n = len(s)
	(s01, s10) = (0, 0)
	a = 0
	for i in range(1, n):
		if s[i - 1:i + 1] == '01':
			s01 += 1
	for i in range(n - 1):
		if s[i:i + 2] == '10':
			s10 += 1
	for i in range(n):
		(curr01, curr10) = (0, 0)
		if s[i] == '0':
			if i > 0:
				if s[i - 1] == '1':
					curr10 -= 1
				else:
					curr01 += 1
			if i < n - 1:
				if s[i + 1] == '1':
					curr01 -= 1
				else:
					curr10 += 1
		else:
			if i > 0:
				if s[i - 1] == '1':
					curr10 += 1
				else:
					curr01 -= 1
			if i < n - 1:
				if s[i + 1] == '1':
					curr01 += 1
				else:
					curr10 -= 1
		if s01 + curr01 == s10 + curr10:
			a += 1
	print(a)


for _ in range(int(input())):
	s = input()
	if s.count('10') - s.count('01') > 1 or s.count('01') - s.count('10') > 1:
		print(1)
	elif s.count('10') == s.count('01'):
		print(len(s) - 2)
	else:
		e = 0
		if s.count('10') > s.count('01'):
			if s[0] == '1':
				e += 1
			if s[-1] == '0':
				e += 1
			print(e)
		else:
			if s[0] == '0':
				e += 1
			if s[-1] == '1':
				e += 1
			print(e)


from collections import defaultdict

def isGoodString(s):
	if s[0] == s[-1]:
		return len(s) - 2
	else:
		return 2
n = int(input())
for _ in range(n):
	s = input()
	print(isGoodString(s))


t = int(input())
for _ in range(t):
	S = str(input())
	zeroone = S.count('01')
	onezero = S.count('10')
	if zeroone == onezero:
		print(len(S) - 2)
	else:
		print(2)


t = int(input())
for i in range(t):
	s = str(input())
	zeroone = s.count('01')
	onezero = s.count('10')
	if zeroone == onezero:
		print(len(s) - 2)
	else:
		print(2)


for i in range(int(input())):
	s = input()
	l = len(s)
	c = 0
	if s[0] == s[l - 1]:
		print(l - 2)
	else:
		print(2)


for i in range(int(input())):
	s = input()
	if s[0] == s[len(s) - 1] == '0':
		ans = len(s) - 2
	elif s[0] == s[len(s) - 1] == '1':
		ans = len(s) - 2
	else:
		ans = 2
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	c1 = s.count('1')
	c10 = s.count('10')
	c01 = s.count('01')
	if c1 == 0 or c1 == n:
		print(n - 2)
	elif c10 == c01:
		print(n - 2)
	else:
		print(2)


def isgood(s):
	n = len(s)
	(a, b) = (0, 0)
	for i in range(1, len(s)):
		t = str(s[i]) + str(s[i - 1])
		if t == '01':
			a += 1
		if t == '10':
			b += 1
	return a == b
for q in range(int(input())):
	s = [int(i) for i in input()]
	if isgood(s):
		print(len(s) - 2)
		continue
	cnt = 0
	s[0] ^= 1
	if isgood(s):
		cnt += 1
	s[0] ^= 1
	s[-1] ^= 1
	if isgood(s):
		cnt += 1
	print(cnt)


t = int(input())
while t > 0:
	t -= 1
	n = input()
	c01 = n.count('01')
	c10 = n.count('10')
	if c10 != c01:
		print(2)
	else:
		print(len(n) - 2)


T = int(input())
for _ in range(T):
	S = input()
	(zero_one, one_zero) = ([], [])
	for i in range(len(S) - 1):
		if S[i] == '0' and S[i + 1] == '1':
			zero_one.append(i)
		if S[i] == '1' and S[i + 1] == '0':
			one_zero.append(i)
	c = 0
	for i in range(len(S)):
		(x, y) = (len(zero_one), len(one_zero))
		if S[i] == '0':
			if i - 1 >= 0:
				if S[i - 1] == '1':
					y -= 1
				if S[i - 1] == '0':
					x += 1
			if i + 1 < len(S):
				if S[i + 1] == '1':
					x -= 1
				if S[i + 1] == '0':
					y += 1
		if S[i] == '1':
			if i - 1 >= 0:
				if S[i - 1] == '0':
					x -= 1
				if S[i - 1] == '1':
					y += 1
			if i + 1 < len(S):
				if S[i + 1] == '0':
					y -= 1
				if S[i + 1] == '1':
					x += 1
		if x == y:
			c += 1
	print(c)


import sys
import math
T = int(input())
for _ in range(T):
	s = input()
	a = s.count('01')
	b = s.count('10')
	if a == b:
		print(len(s) - 2)
	else:
		print(2)


T = int(input())
for _ in range(T):
	S = input()
	(zero_one, one_zero) = ([], [])
	for i in range(len(S) - 1):
		if S[i] == '0' and S[i + 1] == '1':
			zero_one.append(i)
		if S[i] == '1' and S[i + 1] == '0':
			one_zero.append(i)
	if len(zero_one) == len(one_zero):
		print(len(S) - 2)
	else:
		print(2)


t = int(input())
for i in range(t):
	s = input()
	c0 = s.count('01')
	c1 = s.count('10')
	if c0 == c1:
		print(len(s) - 2)
	else:
		print(2)


def inv(s):
	if s == '0':
		return '1'
	return '0'

def ans(s):
	hm = {'10': 0, '01': 0}
	i = 0
	j = 1
	while j < len(s):
		if s[i] + s[j] in hm.keys():
			hm[s[i] + s[j]] += 1
		i += 1
		j += 1
	count = 0
	for i in range(0, len(s)):
		org1 = hm['01']
		org2 = hm['10']
		if i == 0:
			if s[i] + s[i + 1] in hm.keys():
				hm[s[i] + s[i + 1]] -= 1
			else:
				hm[inv(s[i]) + s[i + 1]] += 1
		elif i == len(s) - 1:
			if s[i - 1] + s[i] in hm.keys():
				hm[s[i - 1] + s[i]] -= 1
			else:
				hm[s[i - 1] + inv(s[i])] += 1
		else:
			if s[i] + s[i + 1] in hm.keys():
				hm[s[i] + s[i + 1]] -= 1
			else:
				hm[inv(s[i]) + s[i + 1]] += 1
			if s[i - 1] + s[i] in hm.keys():
				hm[s[i - 1] + s[i]] -= 1
			else:
				hm[s[i - 1] + inv(s[i])] += 1
		if hm['01'] == hm['10']:
			count += 1
		hm['01'] = org1
		hm['10'] = org2
	return count
test_cases = int(input())
while test_cases != 0:
	d = input()
	print(ans(d))
	test_cases -= 1


t = int(input())
for _ in range(t):
	s = input()
	count1 = s.count('01')
	count2 = s.count('10')
	if count1 == count2:
		print(len(s) - 2)
	else:
		print(2)


def solve(s):
	(c01, c10) = (0, 0)
	p = s[0]
	n = len(s)
	for i in range(1, n):
		if p + s[i] == '01':
			c01 += 1
		if p + s[i] == '10':
			c10 += 1
		p = s[i]
	ans = 0
	for i in range(n):
		(d01, d10) = (c01, c10)
		newC = '0' if s[i] == '1' else '1'
		if i - 1 >= 0:
			if s[i - 1] + newC == '01':
				d01 += 1
			if s[i - 1] + newC == '10':
				d10 += 1
			if s[i - 1] + s[i] == '01':
				d01 -= 1
			if s[i - 1] + s[i] == '10':
				d10 -= 1
		if i + 1 < n:
			if newC + s[i + 1] == '01':
				d01 += 1
			if newC + s[i + 1] == '10':
				d10 += 1
			if s[i] + s[i + 1] == '01':
				d01 -= 1
			if s[i] + s[i + 1] == '10':
				d10 -= 1
		if d01 == d10:
			ans += 1
	print(ans)
t = int(input())
while t:
	s = input()
	solve(s)
	t -= 1


T = int(input())
while T > 0:
	s = input()
	(x1, x2) = (0, 0)
	i = 0
	while i < len(s):
		if s[i] == '1':
			x1 += 1
			while i < len(s) - 1 and s[i + 1] == '1':
				i += 1
		elif s[i] == '0':
			x2 += 1
			while i < len(s) - 1 and s[i + 1] == '0':
				i += 1
		i += 1
	if x1 == x2:
		print(2)
	else:
		print(len(s) - 2)
	T -= 1


for _ in range(int(input())):
	s = input()
	a = s.count('01')
	b = s.count('10')
	if a == b:
		print(len(s) - 2)
	else:
		print(2)


t = int(input())
for i in range(t):
	s = input()
	zero_one = s.count('01')
	one_zero = s.count('10')
	if zero_one == one_zero:
		print(len(s) - 2)
	else:
		print(2)


t = int(input())
for _ in range(t):
	s = input()
	c1 = s.count('01')
	c2 = s.count('10')
	c = 2
	if c1 == c2:
		c = len(s) - 2
	print(c)


import sys
input = sys.stdin.readline

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

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

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	S = insr()
	ans.append(len(S) - 2 if S[0] == S[-1] else 2)
outplt(ans)


t = int(input())
for i in range(t):
	s = input()
	count01 = s.count('01')
	count10 = s.count('10')
	if count10 == count01:
		print(len(s) - 2)
	else:
		print(2)


t = int(input())
for i in range(t):
	n = input()
	if n[0] == n[-1]:
		print(len(n) - 2)
	else:
		print(2)


k = int(input())
for i in range(k):
	s = input()
	z = s.count('01')
	o = s.count('10')
	if z == o:
		print(len(s) - 2)
	else:
		print(2)


for _ in range(int(input())):
	a = input()
	arr = []
	t = 0
	o = 0
	for i in range(len(a)):
		arr.append(int(a[i]))
	for j in range(len(a) - 1):
		if arr[j] == 1 and arr[j + 1] == 0:
			t += 1
		elif arr[j] == 0 and arr[j + 1] == 1:
			o += 1
	count = 0
	for x in range(len(a)):
		tp = t
		op = o
		if arr[x] == 1:
			if x < len(a) - 1:
				if arr[x + 1] == 0:
					tp -= 1
				else:
					op += 1
			if x > 0:
				if arr[x - 1] == 0:
					op -= 1
				else:
					tp += 1
		else:
			if x < len(a) - 1:
				if arr[x + 1] == 0:
					tp += 1
				else:
					op -= 1
			if x > 0:
				if arr[x - 1] == 0:
					op += 1
				else:
					tp -= 1
		if tp == op:
			count += 1
	print(count)


for _ in range(int(input())):
	s = input()
	c01 = 0
	c10 = 0
	for i in range(len(s) - 1):
		if s[i:i + 2] == '01':
			c01 += 1
		elif s[i:i + 2] == '10':
			c10 += 1
	s1 = 0
	for i in range(len(s)):
		i01 = 0
		i10 = 0
		if i == 0:
			if s[i] == '1':
				if s[i + 1] == '0':
					i10 -= 1
				else:
					i01 += 1
			elif s[i + 1] == '0':
				i10 += 1
			else:
				i01 -= 1
		elif i == len(s) - 1:
			if s[i] == '1':
				if s[i - 1] == '0':
					i01 -= 1
				else:
					i10 += 1
			elif s[i - 1] == '0':
				i01 += 1
			else:
				i10 -= 1
		elif s[i] == '1':
			if s[i + 1] == '0':
				i10 -= 1
			else:
				i01 += 1
			if s[i - 1] == '0':
				i01 -= 1
			else:
				i10 += 1
		else:
			if s[i + 1] == '0':
				i10 += 1
			else:
				i01 -= 1
			if s[i - 1] == '0':
				i01 += 1
			else:
				i10 -= 1
		if c10 + i10 == c01 + i01:
			s1 += 1
	print(s1)


t = int(input())
for i in range(t):
	string = input()
	l = len(string)
	if string[0] == string[l - 1]:
		print(l - 2)
	else:
		print('2')


for I in range(int(input())):
	a = input()
	if a[0] == a[-1]:
		print(len(a) - 2)
	else:
		print('2')


n = int(input())
for i in range(n):
	s = str(input())
	c_10 = s.count('10')
	c_01 = s.count('01')
	if c_10 == c_01:
		print(len(s) - 2)
	else:
		print(2)


for __ in range(int(input())):
	S = input()
	contador01 = 0
	contador10 = 0
	for inicio in range(len(S) - 1):
		if S[inicio:inicio + 2] == '01':
			contador01 += 1
		if S[inicio:inicio + 2] == '10':
			contador10 += 1
	if contador10 == contador01:
		print(len(S) - 2)
	else:
		print(2)


for _ in range(int(input())):
	a = input()
	ab = a.count('01')
	ba = a.count('10')
	if ab == ba:
		print(len(a) - 2)
	else:
		print('2')


for _ in range(int(input())):
	n = input()
	print(len(n) - 2 if n.count('01') == n.count('10') else 2)


t = int(input())
for i in range(t):
	S = str(input())
	zone = S.count('01')
	ozero = S.count('10')
	if zone == ozero:
		print(len(S) - 2)
	else:
		print(2)


def test(f, p, t10, t01):
	if p == 1:
		if f == '00':
			t10 += 1
		elif f == '01':
			t01 -= 1
		elif f == '10':
			t10 -= 1
		elif f == '11':
			t01 += 1
	elif f == '00':
		t01 += 1
	elif f == '01':
		t01 -= 1
	elif f == '10':
		t10 -= 1
	elif f == '11':
		t10 += 1
	return (t10, t01)
t = int(input())
for _ in range(t):
	s = input()
	x = len(s)
	n10 = 0
	n01 = 0
	for i in range(x - 1):
		if s[i:i + 2] == '10':
			n10 += 1
		if s[i:i + 2] == '01':
			n01 += 1
	ans = 0
	for i in range(x):
		t10 = n10
		t01 = n01
		if i == 0:
			(t10, t01) = test(s[i:i + 2], 1, t10, t01)
		elif i == x - 1:
			(t10, t01) = test(s[i - 1:i + 1], 2, t10, t01)
		else:
			(t10, t01) = test(s[i:i + 2], 1, t10, t01)
			(t10, t01) = test(s[i - 1:i + 1], 2, t10, t01)
		if t10 == t01:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	s1 = s.count('01')
	s2 = s.count('10')
	if s1 == s2:
		print(len(s) - 2)
	else:
		print(2)


t = int(input())
for _ in range(t):
	b = input()
	if b.count('01') == b.count('10'):
		print(len(b) - 2)
	else:
		print(2)


T = int(input())
for i in range(0, T):
	s = input()
	x = s.count('01')
	y = s.count('10')
	if x == y:
		print(len(s) - 2)
	else:
		print(2)


for j in range(int(input())):
	s = input()
	count = 0
	if s.count('01') == s.count('10'):
		print(len(s) - 2)
	else:
		print(2)


t = int(input())
for _ in range(t):
	st = str(input())
	zero = st.count('01')
	one = st.count('10')
	if one == zero:
		print(len(st) - 2)
	else:
		print(2)


T = int(input())
for _ in range(T):
	s = str(input())
	zeroone = s.count('01')
	onezero = s.count('10')
	if zeroone == onezero:
		print(len(s) - 2)
	else:
		print(2)


t = int(input())
while t:
	s = str(input())
	ct01 = s.count('01')
	ct10 = s.count('10')
	if ct01 == ct10:
		print(len(s) - 2)
	else:
		print(2)
	t = t - 1


n = int(input())
for i in range(n):
	a = input()
	zo = a.count('01')
	oz = a.count('10')
	if zo == oz:
		print(len(a) - 2)
	else:
		print(2)


for i in range(int(input())):
	x = input()
	l = len(x)
	print(2 if x[0] != x[-1] else l - 2)


t = int(input())
i = 0
while i < t:
	s = input()
	a = s.count('01')
	b = s.count('10')
	if a == b:
		print(len(s) - 2)
	else:
		print(2)
	i = i + 1