Given a binary string $S$ consisting of only 1’s and 0’s where 1 represents a Square and 0 represents a Circle. The diameter of the circle and the side of the square must be any integer (obviously > 0) . You will have to perfectly inscribe (as shown in the example below) the respective geometric figure at $S$$i+1$ inside of $S$$i$ where $i$ $\epsilon$ $[0,N-2]$, if it is possible. Note that, it will not be possible to inscribe if the dimension of the geometric figure you are perfectly inscribing is not an integer and you will discard the rest of the string. Find the maximum number of circles we can inscribe in a square according to the given string.  
For a given binary string there can be only one geometric figure and this figure is concentric.  
For example : the string 1100 can be represented as the figure below, the first two squares have the same side length and the next two circles have the same diameter.  

Another example : the string 0001 can be represented as the one given below
Again here, we have 3 circles of the same diameter and one square inscribed in them.  

-----Input:-----
The first line contains $N$, the number of strings

Then each of the next $N$ lines contains a binary string $S$.  

-----Output:-----
The $N$ lines of output should have $N$ integers in separate lines, the maximum number of circles we can inscribe in a square according to the given string $S$ .  

-----Constraints-----
- 1 $\leq$ $N$ $\leq$ 103
- 1 $\leq$ length of string $S$ $\leq$ 104

-----Sample Input:-----
3

1110

0010

1001000  

-----Sample Output:-----
1

0

2  

-----Explanation:-----
In  the first case, we can inscribe the string 1110 as :  three squares of side length 4 units (on top of each other) and then  we can inscribe one circle of diameter 4 units.
The answer is 1 since, there is 1 circle inscribed in a square.

In the second case 0010, Let the first two circles be of some diameter 10, we can see that we cannot inscribe another square of any integer dimension inside them.

So, the answer is 0.

In the third case 1001000, we can take the first square of size 10, then inscribe two circles of diameter 5, then we cannot inscribe another square in this since, it will not be of any possible integer dimension and we discard the rest of the string.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for z in range(int(input())):
	s = input()
	n = len(s)
	i = 0
	while i < n and s[i] == '1':
		i += 1
	if i == 0:
		print(0)
	else:
		k = 0
		while i < n and s[i] == '0':
			i += 1
			k += 1
		print(k)


for _ in range(int(input())):
	a = list(input())
	len_a = len(a)
	i = 0
	for i in range(i + 1, len_a):
		if a[i - 1] == '0' and a[i] == '1':
			a = a[:i]
			break
	if '1' in a:
		print(a.count('0'))
	else:
		print(0)


t = int(input())
for x in range(t):
	a = list(input())
	N = len(a)
	i = 0
	for i in range(i + 1, N):
		if a[i - 1] == '0' and a[i] == '1':
			a = a[:i]
			break
	if '1' in a:
		print(a.count('0'))
	else:
		print(0)


for _ in range(int(input())):
	s = list(map(int, list(input())))
	s.append('0')
	y = 0
	if s[0] == 0:
		y = 1
	while s[0] == 0:
		s.remove(0)
	while s[0] == 1:
		s.remove(1)
	z = 0
	while s[0] == 0:
		s.remove(0)
		z += 1
	if y == 1:
		print(0)
	else:
		print(z)


N = int(input())
lst = []
lt = []
count = []
for i in range(N):
	string = input()
	lst.append(string)
for num in lst:
	if num.startswith('1'):
		x = num.find('0')
		y = num.find('1', x)
		if y == -1:
			z = lt.append(len(num[x:]))
		else:
			z = lt.append(len(num[x:y]))
	if num.startswith('0'):
		z = lt.append(0)
for i in lt:
	print(i)


t = int(input())
for i in range(t):
	count = 0
	x = list(input())
	f1 = 0
	f2 = 0
	for i in range(len(x)):
		if x[i] == '1' and f1 == 0 and (f2 == 0):
			f1 = 1
		elif x[i] == '1' and f1 == 1 and (f2 == 0):
			continue
		elif x[i] == '0' and f1 == 0 and (f2 == 0):
			f2 = 1
		elif x[i] == '0' and f1 == 1:
			count = count + 1
			f2 = 2
		elif x[i] == '0' and f2 == 1:
			continue
		elif x[i] == '0' and f2 == 2:
			count = count + 1
		elif x[i] == '1' and f2 == 1:
			break
		elif x[i] == '1' and f2 == 2:
			break
	print(count)


for i in range(int(input())):
	s = input()
	if s.count(s[0]) == len(s):
		print('0')
		continue
	if s[0] == '0':
		print('0')
		continue
	tmp = s.index('0')
	c = 1
	for j in range(tmp + 1, len(s)):
		if s[j] == '0':
			c += 1
		else:
			break
	print(c)


def solve(S):
	if S[0] == '0':
		return 0
	count = 0
	flag = False
	for char in S:
		if char == '0':
			count += 1
			flag = True
		elif char == '1' and (not flag):
			continue
		elif char == '1' and flag:
			break
	return count

def main():
	N = int(input())
	for case in range(N):
		S = input()
		print(solve(S))
	return

def __starting_point():
	main()
__starting_point()


try:
	t = int(input())
	while t:
		n = input()
		x = 0
		f = 0
		if n[0] == '1':
			for i in range(1, len(n)):
				if n[i] == '1' and f == 0:
					continue
				elif n[i] == '0':
					x += 1
					f = 1
					continue
				elif n[i] == '1' and f == 1:
					break
		print(x)
		t -= 1
except:
	pass


for _ in range(int(input())):
	s = input().strip()
	if s[0] == '0' or '1' not in s:
		print(0)
	else:
		ans = 0
		s = s.lstrip('1')
		for i in range(len(s)):
			if s[i] == '1':
				break
			ans += 1
		print(ans)


t = int(input())
while t != 0:
	t -= 1
	string = input()
	s = []
	for i in range(len(string)):
		s.append(int(string[i]))
	sqinc = 0
	for i in range(1, len(s)):
		if s[i - 1] != s[i] and s[i - 1] == 1:
			sqinc += 1
		if s[i - 1] != s[i] and s[i - 1] == 0:
			break
		if s[i - 1] == s[i] and s[i - 1] == 0 and (sqinc > 0):
			sqinc += 1
	print(sqinc)


for t in range(int(input())):
	pts = list(input())
	ans = 0
	if pts[0] == '0':
		ans = 0
	else:
		for i in range(1, len(pts), 1):
			if pts[i] == '0':
				ans = ans + 1
			if pts[i - 1] == '0':
				if pts[i] == '1':
					break
	print(ans)


for _ in range(int(input())):
	a = input()
	count = 0
	if a[0] == '0':
		print(count)
	else:
		s = 0
		for i in a:
			if i == '0':
				count += 1
				s += 1
			elif s > 0:
				break
		print(count)


t = 0
try:
	t = int(input())
except:
	pass
for _ in range(t):
	s = input()
	x = 0
	if s[0] == '0':
		print(x)
	else:
		last = 0
		for i in range(0, len(s)):
			if s[i] == '0':
				x += 1
				if i < len(s) - 1:
					if s[i + 1] == '1':
						break
			else:
				last = 1
		print(x)


for _ in range(int(input())):
	S = input().strip()
	count = 0
	Sflag = False
	Cflag = False
	for x in S:
		if x == '1':
			Sflag = True
		else:
			Cflag = True
		if Cflag and x == '1':
			break
		if Sflag and x == '0':
			count += 1
	print(count)


for N in range(int(input())):
	(count, nxt, prev) = (0, 0, 0)
	S = input()
	S = list(S)
	if S[0] == '1':
		for i in range(1, len(S)):
			if S[i] == '0' and nxt == 0 and (prev == 0):
				for j in range(i, len(S)):
					if S[j] == '0':
						count = count + 1
					if j == len(S) - 1:
						prev = prev + 1
					elif S[j] == '1':
						nxt = nxt + 1
						break
			else:
				continue
	print(count)


n = int(input())
for _ in range(n):
	s = input()
	if s[0] == '0':
		print(0)
	else:
		c = 0
		flag = 0
		for i in range(1, len(s)):
			if s[i] == '0':
				c += 1
				flag = 1
			if s[i] == '1' and flag == 1:
				break
		print(c)


for _ in range(int(input())):
	s = input()
	lis = []
	count = 0
	for i in s:
		lis.append(int(i))
	if lis[0] == 0:
		print(0)
		continue
	i = 0
	while i < len(lis) and lis[i] == 1:
		i += 1
		continue
	while i < len(lis) and lis[i] == 0:
		count += 1
		i += 1
	print(count)


test = int(input())
for tt in range(0, test):
	s = input()
	n = len(s)
	p = 0
	if s[0] == '0':
		print(0)
	else:
		i = 0
		while i < n and s[i] == '1':
			i = i + 1
		while i < n and s[i] == '0':
			p = p + 1
			i = i + 1
		print(p)


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


import re
for _ in range(int(input())):
	m = re.match('1+(0*)', input())
	if m:
		print(len(m[1]))
	else:
		print(0)


T = int(input())
for _ in range(T):
	s = input()
	if s[0] == '0':
		print('0')
		continue
	c = 0
	z = 0
	for i in range(len(s)):
		if s[i] == '1':
			if z == 0:
				continue
			else:
				break
		c += 1
		z = 1
	print(c)


T = int(input())
for _ in range(T):
	S = input()
	t = -1
	if S[0] == '0':
		print(0)
		continue
	else:
		i = 1
		count = 0
		while i < len(S):
			if i == len(S) - 1 and S[i] == '0':
				print(count + 1)
				break
			if t == -1 and i == len(S) - 1:
				print(0)
				break
			if t == 0 and S[i] == '1':
				print(count)
				break
			if S[i] == '0':
				t = 0
			if S[i] == '0' and t == 0:
				count += 1
			i = i + 1