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: interview

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)


# cook your dish h
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)


# cook your dish here
t=int(input())
for x in range(t):
    a = list(input())
    # print(a)
    # flag = 1
    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)
    
  
   
    


# cook your dish here

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()

# cook your dish here
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)


# cook your dish here
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
            else:
                if 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)

# cook your dish here
for N in range(int(input())):
       count,nxt,prev=0,0,0
       S=input()
       S=list(S)
       # print(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
                                          # print(count)
                                   if j==len(S)-1:
                                          prev=prev+1
                                   elif S[j]=='1':
                                          nxt=nxt+1
                                          break
                     else:
                            continue
                            # print(count)
                     # if S[i]=='1' and S[i].count('0')<1:
                     #        # nxt=nxt+1
                     #        continue
       print(count)

# cook your dish here
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)

# cook your dish here
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
    #print(i)
    while i<len(lis) and lis[i]==0:
        count+=1
        i+=1
    print(count)




# cook your dish here
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)

# cook your dish here
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