Polycarp bought a new expensive painting and decided to show it to his $n$ friends. He hung it in his room. $n$ of his friends entered and exited there one by one. At one moment there was no more than one person in the room. In other words, the first friend entered and left first, then the second, and so on.

It is known that at the beginning (before visiting friends) a picture hung in the room. At the end (after the $n$-th friend) it turned out that it disappeared. At what exact moment it disappeared — there is no information.

Polycarp asked his friends one by one. He asked each one if there was a picture when he entered the room. Each friend answered one of three:

no (response encoded with 0);

yes (response encoded as 1);

can't remember (response is encoded with ?).

Everyone except the thief either doesn't remember or told the truth. The thief can say anything (any of the three options).

Polycarp cannot understand who the thief is. He asks you to find out the number of those who can be considered a thief according to the answers.


-----Input-----

The first number $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

The following is a description of test cases.

The first line of each test case contains one string $s$ (length does not exceed $2 \cdot 10^5$) — a description of the friends' answers, where $s_i$ indicates the answer of the $i$-th friend. Each character in the string is either 0 or 1 or ?.

The given regularity is described in the actual situation. In particular, on the basis of answers, at least one friend can be suspected of stealing a painting.

It is guaranteed that the sum of string lengths over the entire input data set does not exceed $2 \cdot 10^5$.


-----Output-----

Output one positive (strictly more zero) number – the number of people who could steal the picture based on the data shown.


-----Examples-----

Input
8
0
1
1110000
?????
1?1??0?0
0?0???
??11
??0??
Output
1
1
2
5
4
1
1
3


-----Note-----

In the first case, the answer is $1$ since we had exactly $1$ friend.

The second case is similar to the first.

In the third case, the suspects are the third and fourth friends (we count from one). It can be shown that no one else could be the thief.

In the fourth case, we know absolutely nothing, so we suspect everyone.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()[:-1]
	a = s.rfind('1')
	b = s.find('0')
	if a == b == -1:
		print(len(s))
	elif a == -1:
		print(b + 1)
	elif b == -1:
		print(len(s) - a)
	else:
		print(b - a + 1)


import sys
sys.stdin.readline()
for line in sys.stdin:
	length = len(line.strip())
	if length == 1:
		print(1)
		continue
	pos0 = line.find('0')
	pos1 = line.rfind('1')
	if pos0 == -1 and pos1 == -1:
		print(length)
	elif pos0 == -1 and pos1 != -1:
		print(length - pos1)
	elif pos0 != -1 and pos1 == -1:
		print(pos0 + 1)
	else:
		print(pos0 - pos1 + 1)


for s in [*open(0)][1:]:
	print(s.find('0') % (len(s) - 1) - max(0, s.rfind('1')) + 1)


def num_thieves(s):
	if s[0] == '0':
		return 1
	elif s[-1] == '1':
		return 1
	elif s == '?' * len(s):
		return len(s)
	elif s.count('1') == 0:
		total = s.find('0') + 1
		return total
	elif s.count('0') == 0:
		total = len(s) - s.rfind('1')
		return total
	else:
		total = s.find('0') - s.rfind('1') + 1
		return total
num_cases = int(input())
answers = []
for i in range(0, num_cases):
	s = str(input())
	answers.append(num_thieves(s))
for ans in answers:
	print(ans)


t = int(input())
out = ''
for _ in range(t):
	info = input()
	ans = 0
	if '0' not in info:
		for i in range(len(info) - 1, -1, -1):
			ans += 1
			if info[i] != '?':
				break
	else:
		for i in range(info.index('0'), -1, -1):
			ans += 1
			if info[i] == '1':
				break
	out += str(ans) + '\n'
print(out)


a = int(input())
b = []
n = 0
for i in range(a):
	c = list(input())
	if '0' in c:
		d = c.index('0')
		f = c[:d + 1]
		f.reverse()
		if '1' in f:
			d = f.index('1')
			n = d + 1
		else:
			n = d + 1
	elif '1' in c:
		c.reverse()
		d = c.index('1')
		n = d + 1
	else:
		for z in c:
			n += 1
	b.append(n)
	n = 0
for i in b:
	print(i, end=' ')
	print()


T = int(input())
q = []
for i in range(T):
	data = input()
	q.append(data)

def solve(data):
	last_1 = 0
	for (idx, c) in enumerate(data):
		if c == '1':
			last_1 = idx
		elif c == '0':
			break
	print(idx - last_1 + 1)
for data in q:
	solve(data)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input()
	n = len(s) - 1
	if n == 1:
		print(1)
	elif s.count('?') == n:
		print(n)
	elif s.count('1') == 0:
		if s.count('0') == n:
			print(1)
		elif s.count('0') == 1:
			print(s.find('0') + 1)
		else:
			x = 0
			i = 0
			while x < 1:
				if s[i] == '0':
					x = x + 1
				i = i + 1
			print(i)
	elif s.count('0') == 0:
		if s.count('1') == n:
			print(1)
		elif s.count('1') == 1:
			print(n - s.find('1'))
		else:
			b = 0
			for i in range(n):
				if s[i] == '1':
					b = i
			print(n - b)
	else:
		z = None
		o = 0
		for i in range(n):
			if s[i] == '0':
				if z:
					continue
				else:
					z = i
			elif s[i] == '1':
				o = i
		if o < z:
			print(z - o + 1)
		elif o == z:
			print(1)
		else:
			c = 0
			for i in range(o + 1):
				if s[i] == '0':
					c = c + 1
			if c > 1:
				print(1)
			else:
				print(2)


import sys
input = sys.stdin.readline

def solve():
	s = input().strip()
	n = len(s)
	one = 0
	zero = 0
	for i in range(n):
		if s[i] == '1':
			one = i + 1
		elif s[i] == '0' and zero == 0:
			zero = i + 1
	if zero and one:
		return abs(zero - one) + 1
	elif zero:
		return zero
	elif one:
		return n - one + 1
	return n
for _ in range(int(input())):
	print(solve())


from bisect import bisect_left, bisect_right
from sys import stdin, setrecursionlimit
from itertools import count, accumulate
from collections import defaultdict, deque, Counter
from functools import reduce, lru_cache
from operator import xor, add
lines = stdin.readlines()
lines.reverse()
setrecursionlimit(10 ** 8)

def input():
	return lines.pop().strip('\n')
t = int(input())
while t:
	s = input()

	def helper():
		n = len(s)
		if n == 1:
			return 1
		(l, r) = (n - 1, 0)
		for i in range(n):
			if s[i] == '0':
				l = i
				break
		for i in range(n - 1, -1, -1):
			if s[i] == '1':
				r = i
				break
		return abs(l - r) + 1
	print(helper())
	t -= 1


import sys
input = lambda : sys.stdin.readline().strip()
a = int(input())
for i in range(a):
	b = input()
	count = 0
	for i in b:
		if i == '?':
			count += 1
		elif i == '0':
			count += 1
			break
		elif i == '1':
			count = 1
	print(count)


l1 = []

def func(s):
	count = 0
	for i in range(len(s)):
		if s[i] == '1':
			count = 1
		elif s[i] == '?':
			count = count + 1
		else:
			count = count + 1
			l1.append(count)
			return
	l1.append(count)
	return
t = int(input())
for i in range(t):
	s = input()
	func(s)
for i in l1:
	print(i)


n = int(input())
result = []
for i in range(n):
	aux = input()
	index_1 = 0
	index_0 = len(aux)
	if '1' in aux and '0' in aux:
		for (i, l) in enumerate(aux):
			if l == '0':
				index_0 = i
				break
		for (i, l) in enumerate(aux):
			if l == '1':
				index_1 = i
		res = index_0 - index_1 + 1
	elif '1' in aux and '0' not in aux:
		for (i, l) in enumerate(aux):
			if l == '1':
				index_1 = i
		index_0 = len(aux)
		res = index_0 - index_1
	elif '0' in aux and '1' not in aux:
		for (i, l) in enumerate(aux):
			if l == '0':
				index_0 = i
				break
		index_1 = -1
		res = index_0 - index_1
	elif '1' not in aux and '0' not in aux:
		res = len(aux)
	result.append(res)
for res in result:
	print(res)


def ans(l):
	n = len(l)
	a = 0
	b = n - 1
	for i in range(n):
		j = n - 1 - i
		if l[j] == '1':
			a = j
			break
	for i in range(n):
		if l[i] == '0':
			b = i
			break
	return b - a + 1
n = int(input())
S = []
for i in range(n):
	l = input()
	S.append(ans(l))
for i in S:
	print(i)


import sys
input = sys.stdin.readline
from math import ceil, floor, gcd

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

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

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

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

def isPrime(n):
	if n == 1:
		return 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return 0
	return 1
t = inp()
for _ in range(t):
	a = input().rstrip()
	n = len(a)
	one = a.count('1')
	zero = a.count('0')
	start = -1
	if one == 0 and zero == 0:
		print(n)
		continue
	if one == 0:
		ans = 0
		for i in range(n):
			ans += 1
			if a[i] == '0':
				break
		print(ans)
		continue
	if zero == 0:
		ans = 0
		for i in range(n - 1, -1, -1):
			ans += 1
			if a[i] == '1':
				break
		print(ans)
		continue
	start = -1
	for i in range(n - 1, -1, -1):
		if a[i] == '1':
			start = i
			break
	end = -1
	for i in range(n):
		if a[i] == '0':
			end = i
			break
	if end < start:
		print(1)
	else:
		print(end - start + 1)


n = int(input())
l = []
for i in range(n):
	a = input()
	l.append(a)
for i in l:
	c = 0
	s = 0
	if len(i) == 1:
		print('1')
	elif i[0] == 0:
		print('1')
	else:
		for j in i:
			if j == '0':
				break
			c = c + 1
			if j == '1':
				s = c
		else:
			if '1' not in i:
				print(c)
			else:
				print(len(i) - s + 1)
		if '0' in i and '1' in i:
			print(i.index('0') - s + 2)
		if '0' in i and '1' not in i:
			print(i.index('0') - s + 1)


n = int(input())
out = []
for i in range(n):
	s = input()
	b = 0
	a = 0
	(case, case2) = (0, 0)
	for i in range(len(s)):
		if s[i] == '1':
			a = i
			case2 = 1
		elif s[i] == '0':
			b = i
			case = 1
			break
	if case == 0:
		if case2 == 0:
			out.append(len(s))
		else:
			out.append(len(s) - a)
		continue
	out.append(b - a + 1)
for i in out:
	print(i)


T = int(input())
for _ in range(T):
	s = list(input())
	if '0' in s:
		end = s.index('0')
		ss = s[:end]
		if '1' in ss:
			ss.reverse()
			strt = ss.index('1')
			print(strt + 2)
		else:
			print(end + 1)
	elif '1' in s:
		s.reverse()
		i = s.index('1')
		print(i + 1)
	else:
		print(len(s))


t = int(input())
while t > 0:
	t -= 1
	s = input()
	if s.find('0') == -1:
		f0 = len(s) - 1
	else:
		f0 = s.index('0')
	if s.find('1') == -1:
		l1 = 0
	else:
		l1 = s.rindex('1')
	print(abs(f0 - l1) + 1)


n = int(input())
for p in range(n):
	a = input()
	st = 0
	fin = len(a)
	if '1' in a:
		st = len(a) - 1 - a[::-1].find('1')
	if '0' in a:
		fin = a.find('0') + 1
	print(fin - st)


def res(s):
	ed = s.rfind('1')
	nul = s.find('0')
	if ed == -1 and nul == -1:
		return len(s)
	elif ed == -1:
		return nul + 1
	elif nul == -1:
		return len(s) - ed
	else:
		return nul - ed + 1
t = int(input())
for _ in range(t):
	s = input()
	print(res(s))


t = int(input())
for i in range(t):
	s = str(input())
	a = -1
	n = len(s)
	b = n
	x = 0
	for j in range(n):
		if s[j] == '1':
			a = j
		elif s[j] == '0':
			b = j
			break
	if a > -1 and b < n:
		x = 2 + (b - a - 1)
	elif a > -1 and b == n:
		x = 1 + (b - a - 1)
	elif a == -1 and b < n:
		x = 1 + b
	else:
		x = n
	print(x)


cnt = int(input())
i = 1
while i <= cnt:
	s = input().strip()
	(lastOne, firstZero) = (0, len(s) - 1)
	for j in range(len(s)):
		if s[j] == '0':
			firstZero = j
			break
	for k in reversed(range(len(s))):
		if s[k] == '1':
			lastOne = k
			break
	print(firstZero - lastOne + 1)
	i += 1


for _ in range(int(input())):
	s = input()
	start = 0
	stop = None
	for (idx, c) in enumerate(s):
		if c == '0':
			stop = idx
			break
		elif c == '1':
			start = idx
	if stop is None:
		ans = len(s) - start
	else:
		ans = stop - start + 1
	print(ans)


def solve(case: str):
	last_seen = case.rfind('1')
	first_missing = case.find('0')
	if last_seen == -1:
		last_seen = 0
	if first_missing == -1:
		first_missing = len(case) - 1
	return first_missing - last_seen + 1
n = int(input())
for _ in range(n):
	case = input()
	print(solve(case))


t = int(input())
for i in range(t):
	s = input()
	l = s.find('0')
	r = s.rfind('1')
	if l != -1 and r != -1:
		print(l - r + 1)
	elif l == -1 and r != -1:
		print(len(s) - r)
	elif l != -1 and r == -1:
		print(l + 1)
	else:
		print(len(s))


for i in range(int(input())):
	s = input()
	n = len(s) - 1
	zero = s.find('0')
	one = s.rfind('1')
	if zero == -1 and one == -1:
		print(n + 1)
	elif zero == -1:
		print(n - one + 1)
	elif one == -1:
		print(zero + 1)
	else:
		print(zero - one + 1)


for t in range(int(input())):
	s = input()
	n = len(s)
	if n == 1:
		print(1)
		continue
	l1 = s.rfind('1')
	l1 = 0 if l1 == -1 else l1
	f0 = s.find('0')
	f0 = n if f0 == -1 else f0 + 1
	print(n - (n - f0) - l1)


for t in range(int(input())):
	s = input()
	l = s.rfind('1')
	l = 0 if l == -1 else l
	f = s.find('0')
	f = len(s) if f == -1 else f + 1
	print(f - l)


_ = int(input())
for __ in range(_):
	s = input()
	out = 0
	if len(s) == 1:
		print(1)
		continue
	if '0' in s:
		out = 1
		for x in range(s.index('0'), -1, -1):
			if s[x] == '?':
				out += 1
			if s[x] == '1':
				out += 1
				break
		print(out)
		continue
	else:
		for x in range(len(s) - 1, -1, -1):
			if s[x] == '1':
				out += 1
				break
			else:
				out += 1
		print(out)


a = int(input())
for i in range(a):
	b = input()
	count = 0
	for i in b:
		if i == '?':
			count += 1
		elif i == '0':
			count += 1
			break
		elif i == '1':
			count = 1
	print(count)


t = int(input())
s = []
for i in range(t):
	s.append(input())
for j in range(t):
	u = s[j]
	m = len(u)
	sum = 0
	ha_um = False
	for i in range(m):
		c = u[i]
		if c == '1':
			sum = 0
			ha_um = True
		elif c == '?':
			sum += 1
		else:
			sum += 1
			break
	if ha_um:
		sum += 1
	print(sum)


t = int(input())
result = []
for i in range(t):
	s = input()
	n = len(s)
	indiceFirstZero = n - 1
	indiceLastOne = 0
	zeroFound = False
	for j in range(n):
		if (s[j] == '0') & (zeroFound == False):
			indiceFirstZero = j
			zeroFound = True
		elif s[j] == '1':
			indiceLastOne = j
	result.append(len(s[indiceLastOne:indiceFirstZero + 1]))
for i in result:
	print(i)


addy = int(input())
for comding in range(addy):
	s = input()
	for j in range(len(s)):
		if s[j] == '0':
			break
	b = s[:j + 1]
	b = b[::-1]
	c = 0
	for x in b:
		if x == '1':
			c += 1
			break
		c += 1
	print(c)


for _ in range(int(input())):
	s = input()
	one = -1
	zero = -1
	for i in range(len(s)):
		if s[i] == '1':
			one = i
		elif s[i] == '0':
			zero = i
			break
	if one == -1 and zero == -1:
		print(len(s))
	elif one == -1:
		print(zero + 1)
	elif zero == -1:
		print(len(s) - one)
	else:
		print(zero - one + 1)


import sys
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
testcases = II()
for testcase in range(testcases):
	s = SI()
	pos1 = 0
	pos0 = len(s)
	for x in range(len(s)):
		if s[x] == '1':
			pos1 = x
		if pos0 == len(s) and s[x] == '0':
			pos0 = x
	mod = 1
	if pos0 == len(s):
		mod -= 1
	print(pos0 - pos1 + mod)


for _ in range(int(input())):
	s = input()
	count = 0
	f = 1
	if len(s) == 1 or s[0] == '0':
		print(1)
	elif s[0] == 1 and len(set(s)) == 1:
		print(1)
	elif s[0] == '?' and len(set(s)) == 1:
		print(len(s))
	else:
		b = 0
		for i in range(len(s)):
			if s[i] == '1':
				b = i
			elif s[i] == '0':
				count = i - b + 1
				f = 0
				break
		if f:
			count = len(s) - b
		print(count)


for _ in range(int(input())):
	s = input()
	ans = 0
	ed = s.count('1')
	n = s.count('0')
	if ed == 0:
		if n == 0:
			ans += len(s)
		else:
			for l in s:
				if l == '0':
					ans += 1
					break
				ans += 1
	else:
		f = s.rfind('1')
		ans += 1
		f += 1
		while f < len(s) and s[f] != '1' and (s[f] != '0'):
			ans += 1
			f += 1
		if f < len(s) and s[f] == '0':
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	L = input()
	a = L.find('0')
	b = L.rfind('1')
	if a < 0 and b >= 0:
		print(len(L) - b)
	elif b < 0 and a >= 0:
		print(a + 1)
	elif a < 0 and b < 0:
		print(len(L))
	elif a < b:
		print(0)
	elif a == b:
		print(1)
	else:
		print(a - b + 1)


for j in range(int(input())):
	k = 1
	s = input()
	if s[0] == '0' or s[-1] == '1' or len(s) == 1:
		print(1)
		continue
	zero = s.count('0')
	one = s.count('1')
	if one > 0 and zero > 0:
		print(s.find('0') - s.rfind('1') + 1)
	elif zero + one == 0:
		print(len(s))
	elif one == 0:
		print(len(s[:s.find('0')]) + 1)
	else:
		print(len(s[s.rfind('1'):]))


for test in range(int(input())):
	st = input()
	sst = st[-1::-1]
	if st[0] == '0' or st[-1] == '1':
		print(1)
	else:
		c = 0
		k = -1
		s = 0
		a = -1
		for i in range(len(st)):
			if st[i] == '1':
				a = i
		o = st.find('0')
		if a == -1 and o == -1:
			print(len(st))
		elif a == -1 and o >= 0:
			print(o + 1)
		elif a >= 0 and o == -1:
			print(len(st) - a)
		else:
			print(o - a + 1)


for i in range(int(input())):
	r = input()
	c = 0
	for j in r:
		if j == '1':
			c = 1
		elif j == '0':
			c += 1
			break
		elif j == '?':
			c += 1
	print(c)


for _ in range(int(input())):
	r = list(input())
	z = len(r) - 1
	o = 0
	if '0' in r:
		z = r.index('0')
	if '1' in r:
		r.reverse()
		o = len(r) - 1 - r.index('1')
	print(z - o + 1)


n = int(input())
for _ in range(n):
	l = list(input())
	if len(l) > 1:
		if '1' in l and '0' in l:
			for i in range(len(l) - 1):
				if l[i] == '1' and l[i + 1] != '1':
					c = i
			print(abs(c - l.index('0')) + 1)
		elif '1' not in l and '0' in l:
			print(l.index('0') + 1)
		elif '1' in l and '0' not in l:
			for i in range(len(l) - 1):
				if l[i] == '1' and l[i + 1] != '1':
					c = i
			if l[-1] == '1':
				print(1)
			else:
				print(abs(len(l) - c))
		else:
			print(len(l))
	else:
		print(1)


x = int(input())
for i in range(x):
	ys = input()
	if len(ys) == 1:
		print('1')
	else:
		if ys[-1] == '1':
			print('1')
			continue
		elif ys[0] == '0':
			print('1')
			continue
		elif '1' not in ys and '0' not in ys:
			print(len(ys))
			continue
		last_one = ys.rfind('1')
		first_zero = ys.find('0')
		if last_one == -1:
			last_one = 0
		if first_zero == -1:
			first_zero = len(ys) - 1
		print(first_zero - last_one + 1)


def solution():
	s = input()
	l = len(s)
	zero_pos = s.find('0')
	one_pos = s.rfind('1')
	if zero_pos == -1:
		zero_pos = l - 1
	if one_pos == -1:
		one_pos = 0
	ans = zero_pos - one_pos + 1
	print(ans)
t = int(input())
for _ in range(t):
	solution()


t = int(input())
for _ in range(t):
	queue = str(input())
	last_one_ind = 0
	first_zero_ind = len(queue) - 1
	for (ind, res) in enumerate(queue):
		if res == '1':
			last_one_ind = ind
		elif res == '0':
			first_zero_ind = ind
			break
	print(first_zero_ind - last_one_ind + 1)


t = int(input(''))
for z in range(t):
	s = input('')
	if '0' not in s:
		r = len(s) - 1
	else:
		r = s.index('0')
	if '1' not in s:
		l = 0
	else:
		l = s.rindex('1')
	print(r - l + 1)


t = int(input(''))
for z in range(t):
	s = input('')
	if s[0] == '0':
		print(1)
	elif s[-1] == '1':
		print(1)
	elif '0' in s:
		b = s.index('0')
		if '1' in s[:b]:
			d = s[:b].rindex('1')
			c = s[d:b].count('?')
			print(c + 2)
		else:
			print(len(s[:b + 1]))
	elif '1' in s:
		f = s.rindex('1')
		print(len(s[f:]))
	else:
		print(s.count('?'))


def solve(s):
	idx_1 = -1
	c = 0
	flag_1 = 0
	flag_0 = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '1':
			c += 1
			idx_1 = i
			flag_1 = 1
			break
	for i in range(idx_1 + 1, len(s)):
		c += 1
		if s[i] == '0':
			flag_0 = 1
			break
	if not flag_0 and (not flag_1):
		return len(s)
	return c

def main():
	t = int(input())
	for _ in range(t):
		s = input()
		print(solve(s))
main()


for i in range(int(input())):
	s = input()
	sus = 0
	zpos = s.find('0')
	opos = s[::-1].find('1')
	if zpos == -1 and opos == -1:
		sus = len(s)
	elif zpos == -1 and opos != -1:
		sus = opos + 1
	elif zpos != -1 and opos == -1:
		sus = zpos + 1
	else:
		sus = abs(len(s) - opos - zpos - 1) + 1
	print(sus)


for i in range(int(input())):
	s = input()
	(x, y) = (max(s.rfind('1'), 0), s.find('0') + 1)
	if y == 0:
		y = len(s)
	print(y - x)


for _ in range(int(input())):
	s = input()
	n = len(s)
	l = n - 1
	r = 0
	for i in range(n):
		if s[i] == '1':
			r = i
		if s[i] == '0':
			l = i
			break
	print(l - r + 1)


for _ in range(int(input())):
	s = input()
	t = s.find('0')
	print(t - max(s.rfind('1'), 0) + 1 if t != -1 else len(s) - max(s.rfind('1'), 0))


t = int(input())
for _ in range(t):
	s = input()
	count = 0
	for x in s:
		if x == '?':
			count += 1
		elif x == '0':
			count += 1
			break
		elif x == '1':
			count = 1
	print(count)


t = int(input())
for _ in range(t):
	s = input()
	if len(s) == 1 or s[0] == '0':
		print(1)
	else:
		if '0' in s:
			s = s[:s.index('0') + 1]
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				break
		print(len(s) - i)


t = int(input())
for i in range(t):
	s = list(input())
	n = len(s)
	if n == 1:
		print(1)
		continue
	try:
		z = s.index('0')
	except ValueError:
		z = None
	if z != None:
		q = 0
		i = z - 1
		while i >= 0:
			if s[i] == '?':
				q += 1
			else:
				q += 1
				break
			i -= 1
		print(q + 1)
		continue
	else:
		rev_s = s[::-1]
		try:
			o = rev_s.index('1')
		except ValueError:
			o = None
		if o != None:
			q = 0
			i = o - 1
			while i >= 0:
				if rev_s[i] == '?':
					q += 1
				else:
					q += 1
					break
				i -= 1
			print(q + 1)
			continue
		else:
			print(n)
			continue


for _ in range(int(input())):
	s = input()
	a = s.rfind('1')
	b = s.find('0')
	if a == -1 and b == -1:
		print(len(s))
	elif a == -1:
		print(b + 1)
	elif b == -1:
		print(len(s) - a)
	else:
		print(b - a + 1)


def count_thiefs(s):
	if len(s) == 1:
		return 1
	idx_0 = s.find('0')
	if idx_0 == -1:
		idx_0 = len(s)
	else:
		idx_0 += 1
	idx_1 = max(s.rfind('1') - 1, -1)
	return idx_0 - idx_1 - 1
t = int(input())
for _ in range(t):
	s = input().strip()
	print(count_thiefs(s))


for _ in range(int(input())):
	s = input()
	if s.count('1') == 0:
		if s.count('0') == 1 and s[-1] == '0' and (len(s) > 1):
			print(len(s))
		elif s.count('0') > 0:
			print(s.index('0') + 1)
		else:
			print(len(s))
	elif s.count('0') == 0:
		s = s[::-1]
		print(s.index('1') + 1)
	else:
		ze = s.index('0')
		nw = s[:ze + 1]
		nw = nw[::-1]
		print(nw.index('1') + 1)


for _ in range(int(input())):
	s = input()
	nt = 0
	if len(s) == 1:
		print(1)
	elif s[0] == '0':
		print(1)
	elif s[-1] == '1':
		print(1)
	elif s.count('?') == len(s):
		print(len(s))
	elif '?' not in s:
		print(2)
	elif '1' in s:
		if '0' in s:
			print(s.index('0') - (len(s) - s[::-1].index('1')) + 2)
		else:
			print(s[::-1].index('1') + 1)
	else:
		print(s.index('0') + 1)


t = int(input())
for _ in range(0, t):
	s = input()
	lastoneind = 0
	onepres = 0
	zeropres = 0
	firstzeroind = len(s) - 1
	for i in range(0, len(s)):
		if s[i] == '1':
			onepres = 1
			lastoneind = i
		elif s[i] == '0' and zeropres == 0:
			zeropres = 1
			firstzeroind = i
	sus = firstzeroind - lastoneind + 1
	print(sus)


t = int(input())
for i in range(t):
	k = 0
	st = input()
	if st[0] == '0' or st[-1] == '1':
		ans = 1
	else:
		n1 = st.rfind('1')
		if n1 > -1:
			n0 = st.find('0', n1)
		else:
			n0 = st.find('0')
		if n0 == -1 and n1 == -1:
			ans = len(st)
		elif n1 == -1:
			ans = n0 + 1
		elif n0 == -1:
			ans = len(st) - n1
		elif n0 > n1:
			ans = n0 - n1 + 1
		else:
			ans = 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	count = 0
	if n == 1 or s[0] == '0' or s[n - 1] == '1':
		print(1)
	elif s.count('1') == 0 and s.count('0') == 0:
		print(n)
	elif s.count('0') == 0:
		s = s[::-1]
		print(s.index('1') + 1)
	elif s[s.index('0') - 1] == '1':
		print(2)
	else:
		s = s[0:s.index('0')]
		s = s[::-1]
		if s.count('1') == 0:
			print(len(s) + 1)
		else:
			print(s.index('1') + 2)


for _ in range(int(input())):
	s = input()
	if s[-1] == '1':
		print(1)
		continue
	if '0' in s:
		i = s.index('0')
	else:
		i = len(s) - 1
	j = i
	while j >= 0 and s[j] != '1':
		j -= 1
	print(i - max(0, j) + 1)


for _ in range(int(input())):
	s = input()
	if len(s) == 1:
		print(1)
	else:
		if s[0] == '0':
			print(1)
			continue
		(ind0, ind1) = (0, len(s) - 1)
		for i in range(len(s) - 1, -1, -1):
			if s[i] == '1':
				ind0 = i
				break
		for (i, val) in enumerate(list(s)):
			if val == '0':
				ind1 = i
				break
		print(ind1 - ind0 + 1)


t = int(input())
for g in range(t):
	st = input()
	l = max(0, st.rfind('1'))
	r = 0
	if st.find('0') != -1:
		r = st.find('0')
	else:
		r = len(st) - 1
	if st[0] == '0' or st[len(st) - 1] == '1':
		print(1)
	else:
		res = 0
		for i in range(l, r + 1):
			if st[i] == '?' or (st[i] == '1' and st[i + 1] == '?') or (st[i] == '0' and st[i - 1] == '?'):
				res += 1
		if res == 0:
			print(2)
		else:
			print(res)


for i in range(int(input())):
	n = input()
	if len(n) == 1:
		print(1)
		continue
	if '0' not in n and '1' not in n:
		print(len(n))
		continue
	if '0' not in n:
		print(n[::-1].find('1') + 1)
		continue
	first_n = n.find('0')
	n = n[:first_n + 1]
	if '1' in n:
		print(first_n - (len(n) - n[::-1].find('1') - 1) + 1)
	else:
		print(len(n))


for num in range(int(input())):
	w = input()
	ch = w.__len__()
	l = 0
	r = ch - 1
	for i in range(ch):
		if w[i] == '1':
			l = i
		elif w[i] == '0' and i < r:
			r = i
	print(r - l + 1)


for _ in range(int(input())):
	testcase = input()
	if (len(testcase) == 1) | (testcase[0] == '0'):
		print('1')
		continue
	elif ('1' not in testcase) & ('0' not in testcase):
		print(len(testcase))
		continue
	rightmost_1 = 0
	leftmost_0 = len(testcase) - 1
	if '1' in testcase:
		rightmost_1 = testcase.rindex('1')
	if '0' in testcase:
		leftmost_0 = testcase.index('0')
	if leftmost_0 == rightmost_1:
		print(1)
		continue
	print(leftmost_0 - rightmost_1 + 1)


def solve(s: str) -> int:
	if len(s) == 1 or s[0] == '0' or s[-1] == '1':
		return 1
	last_known_one = 0
	first_known_zero = len(s) - 1
	for i in range(1, len(s) - 1):
		if s[i] == '0':
			first_known_zero = i
			break
		elif s[i] == '1':
			last_known_one = i
	return first_known_zero - last_known_one + 1
t = int(input())
for _ in range(t):
	print(solve(input()))


import math as m
i = input()
inp = []
for a in range(0, int(i)):
	inp += [input()]
for s in inp:
	last1 = 0
	first0 = len(s) - 1
	pos = 0
	for c in s:
		if c == '1':
			last1 = pos
		elif c == '0':
			first0 = min(first0, pos)
		pos += 1
	print(first0 - last1 + 1)


for t in range(int(input())):
	l = list(input())
	ans = 0
	flag = 0
	for i in l:
		if i == '0':
			ans = ans + 1
			flag = 1
			print(ans)
			break
		elif i == '1':
			ans = 1
		else:
			ans = ans + 1
	if flag == 0:
		print(ans)


t = int(input())
for z in range(t):
	s = input()
	n = len(s)
	one = 0
	zero = 0
	for i in range(n):
		if s[i] == '1':
			one = i + 1
	for i in range(n):
		if s[i] == '0':
			zero = i + 1
			break
	if one == 0 and zero == 0:
		print(n)
	elif one == 0:
		print(zero)
	elif zero == 0:
		print(n - one + 1)
	else:
		print(abs(zero - one) + 1)


import sys
import math
test_cases = int(input())
answers = []
for test in range(test_cases):
	answers.append(input())
for answer in answers:
	suspects = 1
	if answer[0] == '0':
		print(1)
		continue
	for i in range(1, len(answer)):
		prev_char = answer[i - 1]
		curr_char = answer[i]
		if (prev_char == '?' or prev_char == '1') and curr_char == '?':
			suspects += 1
		elif curr_char == '1':
			suspects = 1
		elif curr_char == '0':
			suspects += 1
			break
	print(suspects)


for test in range(int(input())):
	sus = 0
	a = input()
	if len(a) == 1:
		print(1)
	else:
		a = a[::-1].split('0')
		if len(a) > 1:
			sus += 1
		b = a[-1].split('1')
		if len(b) > 1:
			sus += 1
		sus += len(b[0])
		print(sus)


for _ in range(int(input())):
	s = input()
	x = len(s) - 1
	y = 0
	try:
		x = s.index('0')
	except:
		pass
	try:
		y = s[::-1].index('1')
		y = len(s) - y - 1
	except:
		pass
	print(x - y + 1)


def resi():
	a = input()
	n = len(a)
	(poc, kraj) = (0, n - 1)
	for i in reversed(range(n)):
		if a[i] == '1':
			poc = i
			break
	for i in range(n):
		if a[i] == '0':
			kraj = i
			break
	print(kraj - poc + 1)
for _ in range(int(input())):
	resi()


for t in range(int(input())):
	s = input()
	if s[0] == '0' or s[-1] == '1':
		print(1)
		continue
	c1 = s.count('1')
	c0 = s.count('0')
	if c1 == 0 and c0 == 0:
		print(len(s))
	elif c1 != 0 and c0 != 0:
		r1 = 0
		r0 = 0
		for i in range(len(s)):
			if s[i] == '1':
				r1 = i
			if s[i] == '0' and r0 == 0:
				r0 = i
		print(r0 - r1 + 1)
		continue
	elif c1 == 0 and c0 != 0:
		print(s.index('0') + 1)
	elif c1 != 0 and c0 == 0:
		r = 0
		n = len(s)
		for i in range(n):
			if s[i] == '1':
				r = i
		print(n - r)


for t in range(int(input())):
	s = input()
	n = len(s)
	c0 = n - 1
	c1 = 0
	n = len(s)
	for i in range(n):
		if s[i] == '1':
			c1 = i
		elif s[i] == '0' and c0 == n - 1:
			c0 = i
	print(c0 - c1 + 1)


t = int(input())
for i in range(t):
	s = input()
	if len(s) == 1:
		print(1)
	elif s.count('?') == len(s):
		print(len(s))
	elif s.count('0') == len(s) or s.count('1') == len(s):
		print(1)
	elif s.count('0') == 0 and s.count('1') >= 1:
		print(abs(s.rfind('1') - (len(s) - 1)) + 1)
	elif s.count('0') >= 1 and s.count('1') == 0:
		print(s.find('0') + 1)
	elif s.count('1') >= 1 and s.count('0') >= 1:
		print(abs(s.rfind('1') - (s.find('0') + 1)))


def solve():
	s = input()
	n = len(s)
	for i in range(n):
		if s[i] == '0':
			break
	for j in reversed(range(n)):
		if s[j] == '1':
			break
	print(i - j + 1)

def main():
	t = int(input())
	for i in range(t):
		solve()
	return
main()


import math
for _ in range(int(input())):
	s = input()
	total = 0
	check = False
	count1 = s.count('1')
	for i in s:
		if check:
			if i == '?':
				total += 1
			else:
				total += 1
				break
		else:
			if i == '1':
				count1 -= 1
			if count1 == 0:
				if i == '?':
					total += 1
				elif i == '0':
					total += 1
					break
				else:
					total += 1
					check = True
	print(total)