You are given a binary string $s$ (recall that a string is binary if each character is either $0$ or $1$).

Let $f(t)$ be the decimal representation of integer $t$ written in binary form (possibly with leading zeroes). For example $f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$ and $f(000100) = 4$.

The substring $s_{l}, s_{l+1}, \dots , s_{r}$ is good if $r - l + 1 = f(s_l \dots s_r)$.

For example string $s = 1011$ has $5$ good substrings: $s_1 \dots s_1 = 1$, $s_3 \dots s_3 = 1$, $s_4 \dots s_4 = 1$, $s_1 \dots s_2 = 10$ and $s_2 \dots s_4 = 011$. 

Your task is to calculate the number of good substrings of string $s$.

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of queries.

The only line of each query contains string $s$ ($1 \le |s| \le 2 \cdot 10^5$), consisting of only digits $0$ and $1$.

It is guaranteed that $\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$.


-----Output-----

For each query print one integer — the number of good substrings of string $s$.


-----Example-----
Input
4
0110
0101
00001000
0001000

Output
4
3
4
3

Difficulty: interview

Starter code:

Solutions:
LOG = 20

def solve(s):
	n = len(s)
	res = 0
	z = 0
	for t in range(0, n):
		if s[t] == '0':
			z += 1
			continue
		for l in range(1, min(LOG, n - t + 1)):
			x = int(s[t:t+l], 2)
			# print(l, t, x, l + z)
			if l + z >= x:
				res += 1

#			print(t, l, x, res, z)
		z = 0
	return res


t = int(input())
while t > 0:
	t -= 1
	s = input()
	print(solve(s))

t = int(input())


c = [0] * 200100
for _ in range(t):
    s = input()
    for i in range(len(s)):
        c[i] = s[i] == '0'
        if i and s[i] == '0':
            c[i] += c[i-1]

    sol = 0
    for i in range(len(s)):
        tmp = 0
        for k in range(20):
            if i - k < 0:
                break
            
            tmp += (s[i - k] == '1') << k
            if tmp == k + 1:
                sol += 1

        if i >= 20:
            top = 20 + c[i-20]
            if tmp > 20 and tmp <= top:
                sol += 1
    print(sol)
        


T = int(input())
for t in range(T):
    s = input()
    n = len(s)
    res = 0
    zeros = 0
    for i, c in enumerate(s):
        if c == '0':
            zeros += 1
        else:
            tail = 1
            j = 1
            while tail <= zeros+j:
                res += 1
                j += 1
                if i-1+j == n:
                    break
                tail *= 2
                tail += int(s[i-1+j])
            zeros = 0
    print(res)

def main():
    from sys import stdin, stdout
    input = stdin.readline
    print = stdout.write
    for _ in range(int(input())):
        ans = 0
        i = -1
        s = input()
        for j in range(len(s) - 1):
            if s[j] == '1':
                c = 0
                for k in range(j, len(s)):
                    c = c * 2 + (s[k] == '1') + (s[k] == '\n') * k
                    if k - i < c:
                        ans += k - j
                        break
                i = j
        print(f'{ans}\n')


main()


for _ in range(int(input())):
    s = input()
    q1 = ans = 0
    for q in range(len(s)):
        if s[q] == '0':
            q1 += 1
        else:
            ans += 1+(q != len(s)-1 and s[q+1] == '0')
            q2 = size = 1
            for q3 in range(1, q1+1):
                size += 1
                if q2 == size:
                    ans += 1
                while q2 < size and size-q3+q < len(s):
                    q2 *= 2
                    q2 += ord(s[q+size-q3])-ord('0')
                    size += 1
                    if q2 == size:
                        ans += 1
            q1 = 0
    print(ans)


import sys
D = {}
m = 18
for i in range(1, 1<<m):
    D[bin(i)[2:]] = i
for _ in range(int(input())):
    S = sys.stdin.readline().rstrip()
    s = 0
    N = len(S)
    ans = 0
    for i in range(N):
        if S[i] == "1":
            for j in range(1, min(m, N - i) + 1):
                k = D[S[i:i+j]]
                if s + j >= k:
                    ans += 1
            s = 0
        else:
            s += 1
    print(ans)



from bisect import *
strings = []
zeronumber = []
for i in range(1, 200001):
    strings.append(format(i, "b"))
    zeronumber.append(i-i.bit_length())

t = int(input())
for _ in range(t):
    s = input()
    z = 0
    ans = 0
    for i in range(len(s)):
        if s[i] == "0":
            z += 1
            continue
        else:
            for j in range(bisect_right(zeronumber, z)):
                #print(j)
                #print(s[i:i+len(strings[j])], strings[j])
                if i+len(strings[j])-1 <= len(s)-1:
                    if s[i:i+len(strings[j])] == strings[j]:
                        ans += 1
            z = 0
    print(ans)


t = int(input())

for _ in [0]*t:
    s = input()
    stack = []
    zero_count = 0
    ans = 0
    for c in map(int, s):
        new_stack = []
        append = new_stack.append
        if c:
            append((c, zero_count))
            ans += 1
            zero_count = 0
        else:
            zero_count += 1

        for v, zeros in stack:
            v = (v << 1) + c
            need_zeros = v - v.bit_length()
            if need_zeros <= zeros:
                ans += 1
                append((v, zeros))

        stack = new_stack

    print(ans)


q = int(input())
for _ in range(q):
    s=input()
    n=len(s)
    ans=100000000
    r=[0 for i in range(n)]
    for i in range(n-1,-1,-1):
        if(s[i]=='1'):
            ans=i
        r[i]=ans
    ansss=0
    for i in range(n):
        ns=0
        for j in range(r[i],n):
            ns=2*ns+(ord(s[j])-ord('0'))
            if(ns==j-i+1):
                ansss+=1
            if(ns>n):
                break
    print(ansss)

import sys
input = sys.stdin.readline

T = int(input())
for testcases in range(T):
    S=input().strip()
    LEN=len(S)

    zeros=0
    ANS=0

    for i in range(LEN):
        if S[i]=="0":
            zeros+=1
        else:

            for j in range(1,min(22,LEN-i+1)):
                k=int((S[i:i+j]),2)
                if k==0:
                    continue
                #print(i,j,k)
                if zeros>=k-j:
                    ANS+=1

            zeros=0

    print(ANS)

        

    


import sys 
import math 
from collections import defaultdict
input = lambda : sys.stdin.readline().rstrip()

for t in range(int(input())):
  ans = 0
  s = input()

  i = 0
  while i < len(s):
    if s[i] == "1":
      ans += 1
      j = i - 1 
      zero_cnt = 0
      while j >= 0 and s[j] == "0":
        zero_cnt += 1
        j -= 1
      
      k = i 
      b = "1"
      while k + 1 < len(s) and (int(b + s[k+1], 2) - len(b) - 1 <= zero_cnt):
        ans += 1
        b += s[k+1]
        k += 1
    
    i += 1
  
  print(ans)

t=int(input())
for i in range(t):
    a=[int(x) for x in list(input())]
    n=len(a)
    zero=0
    arr=0
    for i in range(n):
        if a[i]==1:
            size=2
            num=1
            arr+=1
            if i!=n-1:
                j=i+1
                if a[j]==1:
                    num*=2+1
                else:
                    num*=2
                    
                while num<=size+zero and num>=size:
                    arr+=1
                    if j==n-1:
                        break
                    j+=1
                    if a[j]==1:
                        num=num*2+1
                    else:
                        num*=2
                    size+=1
            zero=0
        else:
            zero+=1
    print(arr)
       


for _ in range(int(input())):
    s = input()
    num_zero = 0
    ans = 0
    
    length = len(s)
    
    for i in range(length):
        if s[i] == "0": num_zero += 1
        else:
            act_num = 1
            j = i
            
            is_right = True
            
            while j < length and is_right:
                if (act_num-(j-i+1)) <= num_zero:
                    ans += 1
                    j += 1
                   
                    if j < length:
                        act_num = act_num*2+int(s[j])
                else: is_right = False
                   
                    
                
            num_zero = 0
            
    print(ans)

''' CODED WITH LOVE BY SATYAM KUMAR '''

from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys

sys.setrecursionlimit(10 ** 6)  # max depth of recursion
threading.stack_size(2 ** 27)  # new thread will get stack of such size
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7


class MergeFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
        self.lista = [[_] for _ in range(n)]

    def find(self, a):
        to_update = []
        while a != self.parent[a]:
            to_update.append(a)
            a = self.parent[a]
        for b in to_update:
            self.parent[b] = a
        return self.parent[a]

    def merge(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b:
            return
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.num_sets -= 1
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.lista[a] += self.lista[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


def display(string_to_print):
    stdout.write(str(string_to_print) + "\n")


def prime_factors(n):  # n**0.5 complex
    factors = dict()
    for i in range(2, math.ceil(math.sqrt(n)) + 1):
        while n % i == 0:
            if i in factors:
                factors[i] += 1
            else:
                factors[i] = 1
            n = n // i
    if n > 2:
        factors[n] = 1
    return (factors)


def all_factors(n):
    return set(reduce(list.__add__,
                      ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))


def fibonacci_modP(n, MOD):
    if n < 2: return 1
    return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(
        fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD


def factorial_modP_Wilson(n, p):
    if (p <= n):
        return 0
    res = (p - 1)
    for i in range(n + 1, p):
        res = (res * cached_fn(InverseEuler, i, p)) % p
    return res


def binary(n, digits=20):
    b = bin(n)[2:]
    b = '0' * (digits - len(b)) + b
    return b


def is_prime(n):
    """Returns True if n is prime."""
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False
    i = 5
    w = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += w
        w = 6 - w
    return True


def generate_primes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    return prime


factorial_modP = []


def warm_up_fac(MOD):
    nonlocal factorial_modP, fac_warm_up
    if fac_warm_up: return
    factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
    for i in range(2, fac_warm_up_size):
        factorial_modP[i] = (factorial_modP[i - 1] * i) % MOD
    fac_warm_up = True


def InverseEuler(n, MOD):
    return pow(n, MOD - 2, MOD)


def nCr(n, r, MOD):
    nonlocal fac_warm_up, factorial_modP
    if not fac_warm_up:
        warm_up_fac(MOD)
        fac_warm_up = True
    return (factorial_modP[n] * (
            (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD)) % MOD)) % MOD


def test_print(*args):
    if testingMode:
        print(args)


def display_list(list1, sep=" "):
    stdout.write(sep.join(map(str, list1)) + "\n")


def display_2D_list(li):
    for i in li:
        print(i)


def prefix_sum(li):
    sm = 0
    res = []
    for i in li:
        sm += i
        res.append(sm)
    return res


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return list(map(int, stdin.readline().split()))


def get_list():
    return list(map(int, stdin.readline().split()))


memory = dict()


def clear_cache():
    nonlocal memory
    memory = dict()


def cached_fn(fn, *args):
    nonlocal memory
    if args in memory:
        return memory[args]
    else:
        result = fn(*args)
        memory[args] = result
        return result


def ncr(n, r):
    return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))


def binary_search(i, li):
    fn = lambda x: li[x] - x // i
    x = -1
    b = len(li)
    while b >= 1:
        while b + x < len(li) and fn(b + x) > 0:  # Change this condition 2 to whatever you like
            x += b
        b = b // 2
    return x


# -------------------------------------------------------------- MAIN PROGRAM


TestCases = True
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False  # Can not be used clubbed with TestCases WHen using recursive functions, use Python 3


def main():
    li = list(stdin.readline().strip())
    k = 0
    res = 0
    for index, cri in enumerate(li):
        if cri == '0':
            k += 1
        else:
            sm = 0
            for i in range(18):
                try:
                    sm = sm * 2 + int(li[index + i])
                    if i + 1 <= sm <= i + 1 + k:
                        res += 1
                except:
                    a = 1
            k = 0
    print(res)


# --------------------------------------------------------------------- END=


if TestCases:
    for i in range(get_int()):
        main()
else:
    main() if not optimise_for_recursion else threading.Thread(target=main).start()


for _ in range(int(input())):
    s=input()
    n=len(s)
    i=0
    j=0
    c=0
    ans=0
    while(i<n):
        if(s[i]=='0'):
            c+=1
        if(s[i]=='1'):
            x=0
            y=0
            for j in range(i,n):
                x=x*2
                if(s[j]=='1'):
                    x+=1
                # print(x,y,c)
                if(x-y-1<=c):
                    ans+=1
                    # print(i,j)
                else:
                    break
                y+=1
            c=0
        i+=1
    print(ans)

from collections import defaultdict
from math import log2


def zeros(n):
    return n - int(log2(n)) - 1


def binary(n):
    s = ""
    while(n > 0):
        s = str(n & 1) + s
        n = n // 2
    return s


t = int(input())

d = defaultdict(list)
for i in range(1, 2 * 10**5 + 1):
    z = zeros(i)
    d[z].append(i)

for _ in range(t):
    s = input()
    n = len(s)
    zs = [0] * n
    z = 0

    for i in reversed(list(range(n))):
        if (s[i] == '0'):
            z += 1
        else:
            z = 0
        zs[i] = z

    total = 0

    for i in range(n):
        z = zs[i]
        candidates = d[z]

        j = i + z
        for c in candidates:
            cS = binary(c)
            cSL = len(cS)

            jEnd = j + cSL
            if (jEnd > n):
                continue
            if (s[j:jEnd] == cS):
                total += 1

    print(total)


import bisect

def solve(s,ans):
    count = 0
    one = []
    n = len(s)
    for i in range(n):
        if s[i] == '1':
            one.append(i)


    for i in range(n):
        curr = 0
        if s[i] == '0':
            start = bisect.bisect(one,i)
            if start < len(one):
                start = one[start]
            else:
                start = n
        else:
            start = i

        #print(i,start)
        for j in range(start,n):
            curr *= 2
            if s[j] == '1':
                curr += 1
            #print(curr,i,j-i+1,j)
            if curr == j-i+1:
                count += 1

            if curr > n-i:
                break

    ans.append(count)
        

def main():
    t = int(input())
    ans = []
    for i in range(t):
        s = input()
        solve(s,ans)

    for i in ans:
        print(i)

main()


import math

for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = 0
	lg = int(math.log2(n)) + 1
	npfx = 0
	for i in range(n):
		if s[i] == '0':
			npfx += 1
			continue
		ans += 1
		cv = 1
		ln = 1
		for j in range(i + 1, min(i + lg + 1, n)):
			ln += 1
			cv *= 2
			cv += s[j] == '1'
			ans += (ln <= cv) and (ln + npfx >= cv)
		npfx = 0
	print(ans)


from math import log
t=int(input())
aa=[1]
for i in range(100):
    aa.append(aa[-1]*2)
for _ in range(t):
    s=input()
    ii=[]
    co=0
    j=0
    ss={}
    ind=-1
    for i in s:
        if i=="0":
            if ind==-1:
                ind=j
            co+=1
        else:
            if ind!=-1:
                ss[j-1]=ind
            co=0
            ind=-1
        j+=1
    if s[-1]=="0":
        ss[len(s)-1]=ind
    ans=0
    for i in range(1,int(log(len(s))/log(2))+2):
        for j in range(len(s)-i+1):
            st=s[j:j+i]
            if st[0]=="1":
                tot=0
                for ii in range(i):
                    if st[-ii-1]=="1":
                      #  print(ii)
                        tot+=aa[ii]
                le=tot-i
                try:
                    xx=ss[j-1]
                    if (j-xx)>=le:
                        ans+=1
                     #   print(i,j,tot,st)
                except:
                    if le==0:
                        ans+=1
                    #    print(i,j,tot,st)
                    pass
    print(ans)
 #   print()


def run(a, ind, l):
    newSt = ''
    ans = 0
    for i in range(ind, len(a)):
        newSt += a[i]
        if int(newSt, 2) == (i - l + 1):
            ans += 1
        if int(newSt, 2) > (i - l + 1):
            return ans
    return ans


n = int(input())
for kkk in range(n):
    st = input()
    uk = [0] * len(st)
    for i in range(len(uk)):
        uk[i] = i

    for j in range(len(uk)):
        if st[j] == '1':
            uk[0] = j
            break
    for i in range(1, len(uk)):
        if i < uk[i - 1]:
            uk[i] = uk[i - 1]
        else:
            for j in range(i, len(uk)):
                if st[j] == '1':
                    uk[i] = j
                    break

    s = 0
    for i in range(len(uk)):
         if ((uk[i] != i) or st[i] == '1'):
             s += run(st, uk[i], i)
    print(s)

'''input
4
0110
0101
00001000
0001000
'''
for test in range(int(input())):
	s = input()
	ans = 0
	for l in range(1, min(20, len(s))+1):
		p = 0
		for i in range(len(s)-l+1):
			if s[i]=='0':
				p += 1
				continue
			x = int(s[i:i+l], 2)
			if x>=l and (x-l)<=p:
				ans+=1
			p = 0
	print(ans)



from math import log2
from math import ceil

for _ in range(int(input())):
    S = list(map(int, list(input())))
    combs = 0
    maxlen = ceil(log2(len(S)))
    #print(maxlen)
    prezeros = 0
    next1 = [0] * len(S)
    nxt = len(S) - 1
    for i in range(len(S) - 1, -1, -1):
        if S[i] == 1:
            nxt = i
        next1[i] = nxt
    for l in range(len(S)):
        if S[l] == 0:
            nxtl = next1[l]
            val = 0
            lcomb = 0
            for r in range(nxtl, min(nxtl + maxlen + 1, len(S))):
                val = 2 * val + S[r]
                if val == r - l + 1:
                    # print(l, r)
                    lcomb += 1
            combs += lcomb
            continue
        val = 0
        lcomb = 0
        for r in range(l, min(l + maxlen + 1, len(S))):
            val = 2 * val + S[r]
            if val == r - l + 1:
                #print(l, r)
                lcomb += 1
        combs += lcomb
        prezeros = 0
    print(combs)