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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Sorting

Complete search


Solutions:
import os
import heapq
import sys, threading
import math
import bisect
import operator
from collections import defaultdict
sys.setrecursionlimit(10 ** 5)
from io import BytesIO, IOBase

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def power(x, p, m):
	res = 1
	while p:
		if p & 1:
			res = res * x % m
		x = x * x % m
		p >>= 1
	return res

def inar():
	return [int(k) for k in input().split()]

def lcm(num1, num2):
	return num1 * num2 // gcd(num1, num2)

def main():
	t = int(input())
	for _ in range(t):
		string = input()
		n = len(string)
		prefix = [0] * n
		cnt = 0
		for i in range(n - 1):
			if string[i] == '0':
				cnt += 1
			else:
				cnt = 0
			prefix[i + 1] = cnt
		ans = 0
		dic = defaultdict(int)
		for i in range(1, 19):
			if len(string) >= i:
				for j in range(n - i + 1):
					num = string[j:j + i]
					num = int(num, 2)
					if num == i:
						if (num, j) in dic:
							continue
						else:
							ans += 1
						continue
					if num < i:
						continue
					else:
						zeros = prefix[j]
						if zeros + i >= num:
							ad = num - i
							if (num, j - ad) in dic:
								continue
							else:
								ans += 1
								dic[num, j - ad] = 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for case_num in range(t):
	s = input()
	sum = [0]
	for i in s:
		sum.append(sum[-1] + int(i))
	ans = 0
	for i in range(len(s)):
		if s[i] == '1':
			ans += 1
			curr = 1
			j = i + 1
			while j < len(s):
				curr = curr * 2 + int(s[j])
				if curr > j + 1:
					break
				right = j - i + 1
				left = curr - right
				if i >= left and sum[i] == sum[i - left]:
					ans += 1
				else:
					break
				j += 1
	print(ans)


t = int(input())
for _ in range(t):
	s = list(str(input()))
	n = len(s)
	nxt = [-1] * n
	for i in range(n):
		if s[i] == '1':
			nxt[i] = i
		elif i != 0:
			nxt[i] = nxt[i - 1]
	res = 0
	for r in range(n):
		sum_ = 0
		for l in range(r, -1, -1):
			if r - l > 20:
				break
			if s[l] == '0':
				continue
			sum_ += 1 << r - l
			if l == 0:
				if sum_ <= r - -1:
					res += 1
			elif sum_ <= r - nxt[l - 1]:
				res += 1
	print(res)


def decimal(ss):
	ans = 0
	c = 0
	for i in range(len(ss) - 1, -1, -1):
		if ss[i] == '1':
			ans += 2 ** c
		c += 1
	return ans
for _ in range(int(input())):
	s = input()
	ll = len(s)
	zer = [0] * (ll + 1)
	s += '#'
	for i in range(ll):
		if s[i] == '0':
			zer[i + 1] = zer[i] + 1
		else:
			zer[i + 1] = 0
	ans = 0
	for i in range(ll):
		if s[i] == '1':
			for j in range(min(20, ll - i)):
				no = decimal(s[i:i + j + 1])
				if zer[i] + j + 1 >= no:
					ans += 1
	print(ans)


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
from math import *
from collections import defaultdict as dd, deque

def data():
	return sys.stdin.readline().strip()

def mdata():
	return map(int, data().split())
for t in range(int(data())):
	s = input()
	ans = 0
	zero = 0
	for i in range(len(s)):
		if s[i] == '0':
			zero += 1
		else:
			s1 = ''
			for j in range(i, min(len(s), i + 18)):
				s1 += s[j]
				if int(s1, 2) <= zero + j - i + 1:
					ans += 1
			zero = 0
	print(ans)


t = int(input())
for _ in range(t):
	s = [int(i) for i in input().strip()]
	n = len(s)
	left_distance = [0] * n
	left_distance[0] = int(not s[0])
	for i in range(1, n):
		if not s[i]:
			left_distance[i] = left_distance[i - 1] + 1
	ct = 0
	for i in range(n):
		if s[i]:
			cmp = 0
			if i:
				cmp = left_distance[i - 1]
			b = ''
			j = i
			while j < min(i + 20, n):
				b += str(s[j])
				if int(b, 2) <= 1 + j - i + cmp:
					ct += 1
				j += 1
	print(ct)


from sys import stdin

def input():
	return next(stdin)[:-1]

def main():

	def solve():
		ss = input()
		count = 0
		l = 0
		sums = {}
		count = 0
		last1 = -1
		for r in range(len(ss)):
			d = 1 if ss[r] == '1' else 0
			if d == 1:
				sums[last1 + 1, r] = 0
				last1 = r
			for ((ll, lr), v) in list(sums.items()):
				v += v + d
				if v > r - ll + 1:
					del sums[ll, lr]
				else:
					if v <= r - ll + 1 and v >= r - lr + 1:
						count += 1
					sums[ll, lr] = v
		print(count)
	q = int(input())
	for _ in range(q):
		solve()
main()


t = int(input())
a = []
for i in range(t):
	a.append(input())
for i in a:
	p = -1
	l = len(i)
	d = 0
	for j in range(l):
		if i[j] == '1':
			q = j
			s = j - p - 1
			while q < l:
				if q == j + 18:
					break
				f = int(i[j:q + 1], 2)
				r = q - j + 1
				if r + s >= f:
					d += 1
				q += 1
			p = j
	print(d)


for _ in range(int(input())):
	s = input()
	a = 0
	for w in range(1, 20):
		z = 0
		x = int(s[:w - 1], 2) if w > 1 else 0
		for c in range(len(s) - w + 1):
			x <<= 1
			x += s[c + w - 1] == '1'
			a += s[c] == '1' and x >= w and (x - w <= z)
			z = z + 1 if s[c] == '0' else 0
			if s[c] == '1':
				x -= 1 << w - 1
	print(a)


q = int(input())
ans = []
for z in range(q):
	a = [int(i) for i in input()]
	n = len(a)
	kol = 0
	b = [100000] * n
	t = n - 1
	y = 100000
	while t >= 0:
		b[t] = y
		if a[t]:
			y = t
		t -= 1
	for i in range(n):
		kol += a[i]
		d = a[i] * 2
		if a[i]:
			for j in range(i + 1, min(i + 20, n)):
				d += a[j]
				if d == j - i + 1:
					kol += 1
				d *= 2
		else:
			for j in range(b[i], min(b[i] + 20, n)):
				d += a[j]
				if d == j - i + 1:
					kol += 1
				d *= 2
	ans.append(kol)
for i in ans:
	print(i)


inf = 2 * 10 ** 5

def count_occurrences(string, amount_of_zero_left, bit_len):
	ans = 0
	for i in range(0, len(string) - bit_len + 1):
		if string[i] == '1':
			num = int(string[i:i + bit_len], 2)
			rem = num - bit_len
			if num <= inf and rem <= amount_of_zero_left[i]:
				ans += 1
	return ans
inf_bin = len(bin(inf)[2:])
for q in range(0, int(input())):
	s = str(input())
	amount_of_zero_left = [0] * len(s)
	cur_amount = 0
	for bit_len in range(0, len(s)):
		if s[bit_len] == '0':
			cur_amount += 1
		elif s[bit_len] == '1':
			amount_of_zero_left[bit_len] = cur_amount
			cur_amount = 0
	ans = 0
	for bit_len in range(1, inf_bin + 1):
		ans += int(count_occurrences(s, amount_of_zero_left, bit_len))
	print(ans)


t = int(input())
l = [2, 4]
val = 8
cnt = 5
for i in range(2, 200001):
	if cnt == val - 1:
		val *= 2
		cnt += 1
	l.append(cnt)
	cnt += 1
for t1 in range(t):
	s = input()
	n = len(s)
	ans = 0
	cnt = 0
	ind = 0
	while ind < n:
		if s[ind] == '0':
			cnt += 1
		else:
			a = 1
			end = l[cnt]
			while a <= end:
				no = bin(a)[2:]
				if no == s[ind:ind + len(no)]:
					ans += 1
				a += 1
			cnt = 0
		ind += 1
	print(ans)


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)


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)


for test in range(int(input())):
	s = input()
	c = 0
	for i in range(1, min(20, len(s)) + 1):
		p = 0
		for j in range(len(s) + 1 - i):
			if s[j] == '0':
				p += 1
				continue
			x = int(s[j:j + i], 2)
			if x >= i and x - i <= p:
				c += 1
			p = 0
	print(c)


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
				if x - y - 1 <= c:
					ans += 1
				else:
					break
				y += 1
			c = 0
		i += 1
	print(ans)


for i in range(int(input())):
	s = input()
	n = len(s)
	prev = 0
	ans = 0
	dp = [-1] * (n + 1)
	se = set()
	for i in range(n):
		if s[i] == '1':
			dp[i + 1] = i
		else:
			dp[i + 1] = dp[i]
	for i in range(n):
		for j in range(i + 1, min(n + 1, i + 19)):
			e = s[i:j]
			y = int(e, 2)
			if len(e) == y:
				if (i, j) not in se:
					ans += 1
					se.add((i, j))
			elif y > 18:
				if y <= len(e) + i - dp[i] - 1:
					ser = j - y + 1
					if (ser, j) not in se:
						ans += 1
						se.add((ser, j))
	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(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)


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)))
	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:
					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:
				lcomb += 1
		combs += lcomb
		prezeros = 0
	print(combs)


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)


from sys import stdin, stdout
t = int(stdin.readline().strip())
for caso in range(t):
	s = stdin.readline().strip()
	n = len(s)
	ans = 0
	z = [0 for i in range(n)]
	for i in range(n):
		if s[i] == '0':
			z[i] += 1
		if i > 0:
			z[i] += z[i - 1]
		if s[i] == '1':
			z[i] = 0
	for i in range(n):
		x = 1
		aux = ''
		if s[i] == '1':
			for j in range(i, min(n, i + 21)):
				aux += s[j]
				aux1 = 0
				if i > 0:
					aux1 += z[i - 1]
				if int(aux, 2) <= aux1 + x:
					ans += 1
				x += 1
	stdout.write('%d\n' % ans)


for _ in range(int(input())):
	s = input()
	N = len(s)
	ons = [0] * N
	ons[0] = 1 if s[0] == '1' else 0
	for i in range(1, N):
		ons[i] = ons[i - 1] + (1 if s[i] == '1' else 0)
	tot = 0
	for r in range(N):
		l = r
		pln = 0
		while l >= 0 and r - l < 32:
			ss = s[l:r + 1]
			ln = int(ss, base=2)
			ones = ss.count('1')
			if ln <= pln:
				pln = ln
				l -= 1
				continue
			pln = ln
			st = r - ln + 1
			if st < 0:
				break
			cnt = ons[r] - (ons[st - 1] if st - 1 >= 0 else 0)
			if cnt == ones:
				tot += 1
			l -= 1
	print(tot)


import sys

def rint():
	return map(int, sys.stdin.readline().split())
t = int(input())
for tt in range(t):
	s = input()
	nxti = [0] * len(s)
	if s[0] == '1':
		nxti[0] = 0
	else:
		nxti[0] = -1
	for i in range(1, len(s)):
		if s[i] == '1':
			nxti[i] = i
		else:
			nxti[i] = nxti[i - 1]
	cnt = 0
	for r in range(len(s)):
		sumv = 0
		for l in range(r, max(-1, r - 22), -1):
			assert l >= 0
			if s[l] == '1':
				sumv += 1 << r - l
				if l == 0:
					ll = -1
				else:
					ll = nxti[l - 1]
				max_len = r - ll
				assert max_len >= 1
				if sumv <= max_len:
					cnt += 1
	print(cnt)


for _ in range(int(input())):
	st = input()
	pre = 0
	dic = {}
	le = len(st)
	for i in range(le):
		if st[i] == '0':
			pre += 1
		else:
			dic[i - 1] = pre
			pre = 0
	dic[i] = pre
	ans = 0
	for i in dic:
		tem = ''
		temle = dic[i]
		for j in range(i + 1, le):
			tem += st[j]
			temle += 1
			nu = int(tem, 2)
			if nu <= temle:
				ans += 1
			else:
				break
	print(ans)


ii = lambda : int(input())
kk = lambda : map(int, input().split())
ll = lambda : list(kk())
for _ in range(ii()):
	l = 0
	cnt = 0
	ls = []
	for d in input():
		if d == '1':
			ls.append(l)
		l += 1
	if not ls:
		print(0)
		continue
	ls = list(reversed(ls))
	minl = 0
	for end in range(l - 1, -1, -1):
		num = 0
		while minl < len(ls) and end < ls[minl]:
			minl += 1
		if minl == len(ls):
			break
		i = minl
		while i < len(ls) and num <= l:
			num += 1 << end - ls[i]
			if end - num >= -1 and (len(ls) == i + 1 or ls[i + 1] <= end - num):
				cnt += 1
			i += 1
	print(cnt)


import os
from io import BytesIO, IOBase
import sys
po = [1]
for i in range(17):
	po.append(po[-1] * 2)

def solve(s, x, y, a):
	(ans, su, j) = (0, 0, x)
	while j < y:
		su += s[j] * po[j - x]
		if su >= j - x + 1 and a[j + 1] - x >= su:
			ans += 1
			j = a[j + 1] - 1
		j += 1
	return ans

def main():
	for _ in range(int(input())):
		s = list(map(int, input().rstrip()))
		s.reverse()
		(n, ans) = (len(s), 0)
		a = [n] * (n + 1)
		for i in range(n - 1, -1, -1):
			a[i] = a[i + 1]
			if s[i]:
				a[i] = i
		for i in range(n):
			z = solve(s, i, min(i + 18, n), a)
			ans += z
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	ln = [int(x) for x in input()]
	(sz, zc, ans) = (len(ln), 0, 0)
	for i in range(sz):
		if ln[i] == 1:
			(num, rl) = (0, min(i + 20, sz))
			for j in range(i, rl):
				num = num * 2 + ln[j]
				if j - i + 1 + zc >= num:
					ans += 1
			zc = 0
		else:
			zc += 1
	print(ans)


from collections import defaultdict
import math
n = int(input())
requests = [x for _ in range(n) for x in input().split(' ')]
for _input in requests:
	result = 0
	prev_1_positions = [None] * len(_input)
	for (i, _s) in enumerate(_input):
		if _s == '0':
			if i == 0:
				prev_1_positions[i] = -1
			else:
				prev_1_positions[i] = prev_1_positions[i - 1]
		else:
			prev_1_positions[i] = i
	for (end, _s) in enumerate(_input):
		f_end_start = 0
		for start in reversed(range(0, end + 1)):
			if end - start > 20:
				break
			if _input[start] == '0':
				continue
			f_end_start += 1 << end - start
			max_len_here = end - prev_1_positions[start - 1] if start != 0 else end + 1
			if max_len_here >= f_end_start:
				result += 1
	print(result)


t = int(input())
for nt in range(t):
	s = input()
	n = len(s)
	ans = 0
	for i in range(n):
		if s[i] == '1':
			j = i - 1
			while j > -1 and s[j] == '0':
				j -= 1
			cntzero = i - j - 1
			j = i
			number = 0
			while j < n:
				number = number * 2 + int(s[j])
				if number > cntzero + j - i + 1:
					break
				j += 1
				ans += 1
	print(ans)


ll = lambda : list(map(int, input().split()))
testcases = 1
[testcases] = ll()
for _ in range(testcases):
	s = input()
	n = len(s)
	dp = [0] * (n + 1)
	dp[0] = int(s[0] == '0')
	for i in range(1, n):
		if s[i] == '1':
			dp[i] = 0
		else:
			dp[i] = dp[i - 1] + 1
	ans = 0
	for i in range(n):
		sub = ''
		num = 0
		l = 0
		if s[i] == '1':
			for j in range(0, min(n - i + 1, 30)):
				try:
					num *= 2
					if num == 0 and s[i + j] == '1':
						msd = i + j
					num += int(s[i + j] == '1')
					sub += s[i + j]
				except:
					continue
				if i == 0:
					ans += num == j + 1
				elif num - dp[i - 1] <= j + 1 and num >= j + 1:
					ans += 1
	print(ans)


def f(l, r):
	a = u[l:r + 1]
	m = len(a)
	m1 = 0
	for i in range(m):
		m1 += a[i] * 2 ** (m - i - 1)
	return m1 == m
for _ in range(int(input())):
	s = input()
	u = list(map(int, list(s)))
	n = len(u)
	ans = 0
	for a in range(1, min(19, n) + 1):
		p = 0
		for i in range(n - a + 1):
			if u[i] == 0:
				p += 1
				continue
			q = int(s[i:i + a], 2)
			if q - a <= p and q >= a:
				ans += 1
			p = 0
	print(ans)


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())
ans = []
for _ in range(t):
	s = input()
	n = len(s)
	count = 0
	la = []
	prev = -1
	for i in range(n):
		st = []
		for j in range(i, min(i + 18, n)):
			st.append(s[j])
			z = int(''.join(st), 2)
			if z >= len(st) and st[0] == '1':
				k = z - len(st)
				start = i - k
				end = i - 1
				if z == len(st):
					count += 1
					continue
				if prev < i - k:
					count += 1
		if s[i] == '1':
			prev = i
	ans.append(count)
print(*ans)


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

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def nCr(n, k):
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0):
	hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

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

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

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

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
for _ in range(int(input())):
	s = input().strip()
	n = len(s)
	(z, ans) = (0, 0)
	for i in range(n):
		if s[i] == '0':
			z += 1
		else:
			x = []
			for j in range(i, min(n, i + 19)):
				x.append(s[j])
				k = ''.join(x)
				if len(k) + z >= int(k, 2):
					ans += 1
			z = 0
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	(z, ans) = (0, 0)
	for i in range(n):
		if s[i] == '0':
			z += 1
		else:
			for j in range(1, n + 1):
				if i + j > n:
					break
				x = int(s[i:i + j], 2)
				if z + j >= x:
					ans += 1
				else:
					break
			z = 0
	print(ans)


for _ in range(int(input())):
	st = input()
	(p, i, x) = (0, 0, 0)
	ans = 0
	for i in range(1, min(20, len(st)) + 1):
		p = 0
		for j in range(len(st) - i + 1):
			if st[j] == '0':
				p += 1
			else:
				x = int(st[j:j + i], 2)
				if p + i >= x:
					ans += 1
				p = 0
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	l = len(bin(len(s))) - 2
	ans = 0
	num_1 = []
	num_0 = 0
	for char in s:
		if char == '0':
			num_0 += 1
			num_1.append(-1)
		else:
			num_1.append(num_0)
			num_0 = 0
	for j in range(len(s)):
		if num_1[j] == -1:
			continue
		for k in range(l):
			if j + k + 1 > len(s):
				break
			f = int(s[j:j + k + 1], 2)
			if f - k - 1 > num_1[j]:
				break
			ans += 1
	print(ans)


from sys import setcheckinterval, stdin, setrecursionlimit
setcheckinterval(1000)
setrecursionlimit(10 ** 7)

def iin():
	return int(stdin.readline())

def lin():
	return list(map(int, stdin.readline().split()))
for _ in range(iin()):
	a = input()
	n = len(a)
	a1 = []
	for i in range(n):
		if a[i] == '1':
			a1.append(i)
		else:
			a1.append(a1[-1] if i > 0 else -1)
	ans = 0
	for r in range(n):
		sol = 0
		l = r
		while l >= 0 and r - l < 20:
			if a[l] == '1':
				sol += 1 << r - l
				if sol <= r - (a1[l - 1] if l > 0 else -1):
					ans += 1
			l -= 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	ans = 0
	l = 0
	a = []
	o = [0]
	for c in s:
		l += 1
		if c == '0':
			a = [(2 * val, len + 1) for (val, len) in a]
			o.append(o[-1])
		else:
			a = [(2 * val + 1, len + 1) for (val, len) in a]
			a.append((1, 1))
			o.append(o[-1] + 1)
		a = list(filter(lambda x: x[0] <= l, a))
		for x in a:
			if o[l - x[0]] == o[l - x[1]]:
				ans += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import factorial
from collections import Counter, defaultdict
from heapq import heapify, heappop, heappush

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 1000000007
INF = float('inf')

def main():
	for _ in range(N()):
		s = [int(i) for i in input()]
		le = len(s)
		res = 0
		zn = 0
		for i in range(le):
			if s[i] == 1:
				sm = 0
				for r in range(i, min(le, i + 20)):
					sm = sm * 2 + s[r]
					if sm - (r - i + 1) <= zn:
						res += 1
				zn = 0
			else:
				zn += 1
		print(res)
main()


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)


ii = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
si = lambda : input()
msi = lambda : map(int, stdin.readline().split())
lsi = lambda : list(msi())
t = ii()
for _ in range(t):
	s = si()
	n = len(s)
	c = 0
	ans = 0
	for i in range(n):
		if s[i] == '0':
			c += 1
		else:
			sum = 0
			y = 0
			for j in range(i, n):
				sum = sum * 2 + (s[j] == '1')
				y += 1
				if c + y >= sum:
					ans += 1
				else:
					break
			c = 0
	print(ans)


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)


import math
import sys
from collections import defaultdict
rt = lambda : map(int, input().split())
ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))

def solve(a):
	n = len(a)
	pref0 = [0] * n
	for i in range(n):
		if i == 0:
			pref0[i] = 0
		else:
			pref0[i] = pref0[i - 1] + 1 if a[i - 1] == 0 else 0
	res = 0
	for (i, val) in enumerate(a):
		if val == 1:
			j = i
			curr = 0
			while j < n:
				curr = 2 * curr + a[j]
				curr_len = j - i + 1
				zpref = curr - curr_len
				if zpref > i or zpref > pref0[i]:
					break
				res += 1
				j += 1
	return res

def main():
	T = ri()
	for _ in range(T):
		print(solve(list(map(int, input()))))
main()


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)
			if l + z >= x:
				res += 1
		z = 0
	return res
t = int(input())
while t > 0:
	t -= 1
	s = input()
	print(solve(s))


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)
threading.stack_size(2 ** 27)
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):
	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):
	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):
	global 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):
	global 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 map(int, stdin.readline().split())

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

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

def cached_fn(fn, *args):
	global 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:
			x += b
		b = b // 2
	return x
TestCases = True
fac_warm_up_size = 10 ** 5 + 100
optimise_for_recursion = False

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)
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


def calc(s):
	return int(s, 2)
for nt in range(int(input())):
	s = input()
	n = len(s)
	pref = [-1] * n
	for i in range(n):
		if s[i] == '1':
			pref[i] = i
		else:
			pref[i] = pref[i - 1]
	ans = 0
	for i in range(18):
		for j in range(n - 1, i - 1, -1):
			temp = s[j - i:j + 1]
			if calc(temp) == i + 1 and temp[0] == '1':
				ans += 1
			elif s[j - i] == '1' and j - i - 1 >= 0 and (calc(temp) > i + 1) and (calc(temp) <= j - pref[j - i - 1]):
				ans += 1
	print(ans)


import sys

def main():
	t = int(sys.stdin.readline().strip())
	for _ in range(t):
		s = sys.stdin.readline().strip()
		c0 = ord('0')
		s = [ord(c) - c0 for c in s]
		res = 0
		n = len(s)
		zeros = 0
		for i in range(n):
			if s[i] == 0:
				zeros += 1
				continue
			j = 0
			cur = 0
			while i + j < n:
				cur = cur * 2 + s[i + j]
				need_zeros = cur - j - 1
				if need_zeros <= zeros:
					res += 1
				else:
					break
				j += 1
			zeros = 0
		print(res)
main()


def binaryToDecimal(n):
	return int(n, 2)
t = int(input())
for _ in range(t):
	s = input()
	ct = 0
	zr = 0
	for i in range(len(s)):
		if s[i] == '0':
			zr += 1
		else:
			for j in range(i, len(s)):
				if binaryToDecimal(s[i:j + 1]) <= zr + j - i + 1:
					ct += 1
				else:
					break
			zr = 0
	print(ct)


def f(s):
	res = 0
	cc = 0
	for i in range(len(s)):
		if s[i] == '0':
			cc += 1
		else:
			for j in range(i + 1, len(s) + 1):
				num = int(s[i:j], 2)
				if num >= j - i and num <= j - i + cc:
					res += 1
				if num > j - i + cc:
					break
			cc = 0
	return res
Q = int(input().strip())
for q in range(Q):
	s = input().strip()
	r = f(s)
	print(r)


for i in range(int(input())):
	s = input()
	n = len(s)
	t = [0] * n
	for i in range(n):
		if s[i] == '1':
			t[i] = i
		else:
			t[i] = -1 if i == 0 else t[i - 1]
	res = 0
	for i in range(n):
		sm = 0
		j = i
		while j >= 0 and i - j < 20:
			if s[j] == '0':
				j -= 1
				continue
			sm += 1 << i - j
			if sm <= i - (-1 if j == 0 else t[j - 1]):
				res += 1
			j -= 1
	print(res)


import sys
from collections import deque
IS_LOCAL = False

def read_one(dtype=int):
	return dtype(input())

def read_multiple(f, dtype=int):
	return f(map(dtype, input().split()))

def swap(x, y):
	return (y, x)

def solve_pos(s, k):
	res = 0
	x = 0
	for (i, c) in enumerate(s):
		if c == '0':
			x *= 2
		else:
			x = x * 2 + 1
		if x > k + i + 1:
			break
		res += 1
	return res

def solve(s):
	(res, zeros) = (0, 0)
	for (i, c) in enumerate(s):
		if c == '0':
			zeros += 1
			continue
		if c == '1':
			res += solve_pos(s[i:], zeros)
			zeros = 0
	print(res)

def main():
	T = 4
	xs = ['0110', '0101', '00001000', '0001000']
	if not IS_LOCAL:
		T = read_one(int)
		for _ in range(T):
			s = input()
			solve(s)
	else:
		for s in xs:
			solve(s)
if len(sys.argv) > 1 and sys.argv[1] == 'True':
	IS_LOCAL = True
main()


t = int(input())
for i in range(t):
	st = input()
	n = len(st)
	st = '1' + st
	res = 0
	first1 = n
	for i in range(n, 0, -1):
		sum = 0
		p2 = 1
		for j in range(i, max(i - 18, 0), -1):
			sum += p2 * (st[j] == '1')
			p2 *= 2
			if sum == i - j + 1:
				res += 1
		while first1 > max(i - 18, 0) or st[first1] != '1':
			first1 -= 1
		if i - first1 >= sum and sum > 18:
			res += 1
	print(res)


for _ in range(int(input())):
	s = input()
	n = len(s)
	a = [0] * n
	l = 0
	for i in range(n):
		if s[i] == '0':
			l += 1
		a[i] = l
		if s[i] == '1':
			l = 0
	ans = 0
	for i in range(n):
		if s[i] == '1':
			sn = ''
			for j in range(i, min(n, i + 20)):
				sn += s[j]
				if int(sn, 2) <= j - i + 1 + a[i]:
					ans += 1
	print(ans)


def bin(s):
	return int(s, 2)
for _ in range(int(input())):
	s = str(input())
	q = 0
	ans = 0
	for i in range(len(s)):
		if s[i] == '1':
			for ii in range(i, len(s)):
				string = s[q:ii + 1]
				if bin(string) <= ii + 1 - q:
					ans += 1
				else:
					break
			q = i + 1
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for you in range(t):
	s = input()
	n = len(s) - 1
	ans = 0
	z = [n - 1 for i in range(n)]
	curr = n - 1
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			curr = i
		z[i] = curr
	for i in range(n):
		ok = 0
		for j in range(max(z[i] - 20, i), n):
			ok = 2 * ok + int(s[j])
			if ok > n:
				break
			if ok == j - i + 1:
				ans += 1
	print(ans)


def decimal(s, e, k):
	a = 0
	m = 1
	for j in range(e, s - 1, -1):
		a += k[j] * m
		m *= 2
	return a
for _ in range(int(input())):
	k = [int(i) for i in input()]
	n = len(k)
	zer = [0] * n
	for i in range(1, n):
		if k[i - 1] == 0:
			zer[i] = zer[i - 1] + 1
		else:
			zer[i] = 0
	ans = 0
	for i in range(n):
		if k[i] == 0:
			continue
		else:
			for j in range(i, min(n, 21 + i), 1):
				le = j - i + 1
				an = decimal(i, j, k)
				if an < le:
					p = 0
				elif an <= le + zer[i]:
					ans += 1
	print(ans)


t = int(input())
for i in range(t):
	s = input()
	n = len(s)
	st = []
	for i in range(n):
		st.append(s[n - 1 - i])
	st += '1'
	ans = 0
	last1 = 0
	for i in range(n):
		sum = 0
		p2 = 1
		for j in range(i, min(i + 18, n), 1):
			sum += p2 * (st[j] == '1')
			p2 *= 2
			if sum == j - i + 1:
				ans += 1
		while last1 < min(i + 18, n) or st[last1] != '1':
			last1 += 1
		if last1 - i >= sum and sum > 18:
			ans += 1
	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
from bisect import *
zz = 1
sys.setrecursionlimit(10 ** 5)
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')
di = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def fori(n):
	return [fi() for i in range(n)]

def inc(d, c, x=1):
	d[c] = d[c] + x if c in d else x

def ii():
	return input().rstrip()

def li():
	return [int(xx) for xx in input().split()]

def fli():
	return [float(x) for x in input().split()]

def comp(a, b):
	if a > b:
		return 2
	return 2 if a == b else 0

def gi():
	return [xx for xx in input().split()]

def gtc(tc, ans):
	print('Case #' + str(tc) + ':', ans)

def cil(n, m):
	return n // m + int(n % m > 0)

def fi():
	return int(input())

def pro(a):
	return reduce(lambda a, b: a * b, a)

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

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

def gh():
	sys.stdout.flush()

def isvalid(i, j, n, m):
	return 0 <= i < n and 0 <= j < m

def bo(i):
	return ord(i) - ord('a')

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)
t = fi()
uu = t
while t > 0:
	t -= 1
	s = ii()
	n = len(s)
	a = []
	for i in range(n):
		if s[i] == '1':
			a.append(i)
	ans = 0
	for i in range(n - 1, -1, -1):
		c = 0
		for j in range(i, max(-1, i - 21), -1):
			c += int(s[j]) * 2 ** (i - j)
			if i + 1 < c:
				break
			if s[j] == '1':
				w = bisect_left(a, i - c + 1)
				if a[w] == j:
					ans += 1
	print(ans)


from sys import stdin
from sys import setrecursionlimit as SRL
SRL(10 ** 7)
rd = stdin.readline
rrd = lambda : map(int, rd().strip().split())
T = int(input())
while T:
	s = ''.join(map(str, rd().strip()))
	ans = 0
	max0 = 0
	for i in range(len(s)):
		if s[i] == '0':
			max0 += 1
		else:
			ans += 1
			tot = 1
			for j in range(1, 20):
				tot = tot << 1
				if i + j < len(s):
					if s[i + j] == '1':
						tot += 1
					if max0 >= tot - j - 1:
						ans += 1
			max0 = 0
	print(ans)
	T -= 1


import sys
import math
from collections import defaultdict, deque
import heapq
mod = 10 ** 9 + 7
t = int(sys.stdin.readline())
for _ in range(t):
	s = sys.stdin.readline()[:-1]
	n = len(s)
	dp = [0 for x in range(n + 1)]
	cnt = 0
	ans = 0
	for i in range(n):
		if s[i] == '0':
			cnt += 1
		dp[i + 1] = cnt
	for i in range(n - 1, -1, -1):
		num = 0
		cnt1 = 0
		vis = defaultdict(int)
		for j in range(i, max(i - 20, -1), -1):
			if s[j] == '0':
				num = num
			else:
				num = num + (1 << cnt1)
			cnt1 += 1
			if i - num + 1 >= 0:
				if dp[j] - dp[i - num + 1] == j - (i - num + 1) and num > 0 and (i - num + 1 <= j) and (vis[num] == 0):
					ans += 1
					vis[num] += 1
	print(ans)


def main():

	def solve():
		ss = input()
		count = 0
		l = 0
		sums = {}
		count = 0
		last1 = -1
		for r in range(len(ss)):
			d = 1 if ss[r] == '1' else 0
			if d == 1:
				sums[last1 + 1, r] = 0
				last1 = r
			for ((ll, lr), v) in list(sums.items()):
				v += v + d
				if v > r - ll + 1:
					del sums[ll, lr]
				else:
					if v <= r - ll + 1 and v >= r - lr + 1:
						count += 1
					sums[ll, lr] = v
		print(count)
	q = int(input())
	for _ in range(q):
		solve()
main()


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

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

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

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

def ws(s):
	sys.stdout.write(s + '\n')

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

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def fun(x):
	tt1 = x[:]
	tt = len(x)
	x = ''.join(x)
	x = int(x, 2)
	if x - tt <= cnt:
		return True
	return False
t = 1
t = int(input())
for _ in range(t):
	s = list(si())
	n = len(s)
	cnt = 0
	res = 0
	for i in range(n):
		if s[i] == '0':
			cnt += 1
		else:
			x = []
			for j in range(i, n):
				x += s[j]
				if fun(x):
					res += 1
				else:
					break
			cnt = 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()
	block = min(20, len(s))
	zeros = [0] * len(s)
	count = 0
	ans = 0
	for i in range(len(s)):
		zeros[i] = count
		if s[i] == '1':
			count = -1
		count += 1
	for r in range(len(s) - 1, -1, -1):
		for l in range(r, r - block, -1):
			if l < 0:
				break
			if s[l] == '1':
				if r - l + 1 + zeros[l] >= int(s[l:r + 1], 2):
					ans += 1
	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)


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
		for j in range(start, n):
			curr *= 2
			if s[j] == '1':
				curr += 1
			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()


for t in range(int(input())):
	s = input()
	count = 0
	x = s.count('0')
	if x == len(s):
		print(0)
		continue
	last = 0
	for i in range(len(s)):
		val = 0
		if s[i] == '1':
			for j in range(i, min(i + 18, len(s))):
				if s[j] == '0':
					val *= 2
				else:
					val = val * 2 + 1
				if val <= j - last + 1:
					count += 1
			last = i + 1
	print(count)


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)


t = int(input())
for _ in range(t):
	s = input()
	ct = int(0)
	ans = int(0)
	for i in range(len(s)):
		if s[i] == '0':
			ct += 1
		else:
			num = int(0)
			for j in range(i, len(s)):
				num *= 2
				if s[j] == '1':
					num += 1
				if num <= ct + j - i + 1:
					ans += 1
				if num > j - i + 1 + ct:
					break
			ct = 0
	print(ans)


t = int(input())
nm = {}
for i in range(1, 200001):
	nm[format(i, 'b')] = i
while t > 0:
	s = input()
	sm = [0]
	for c in s:
		sm.append(sm[-1] + (1 if c == '1' else 0))
	ans = 0
	for sz in range(1, 20):
		for i in range(0, len(s) - sz + 1):
			if s[i:i + sz] in nm:
				num = nm[s[i:i + sz]]
				if num == sz:
					ans += 1
				else:
					li = i + sz - num
					if li >= 0 == sm[i] - sm[li]:
						ans += 1
	print(ans)
	t -= 1


a = int(input())
for i in range(a):
	s = input()
	cnt = 1
	ans = []
	index = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			cnt += 1
		else:
			ans.append([cnt, s[i - 1], index])
			cnt = 1
			index = i
	ans.append([cnt, s[-1], index])
	total = s.count('1') + s.count('10')
	if ans[0][1] == '1':
		ans.pop(0)
	if len(ans) == 0:
		print(total)
		continue
	cnt = ans[0][0]
	for i in range(1, len(ans)):
		if i % 2 == 0:
			cnt = ans[i][0]
			continue
		t = ans[i][2]
		g1 = 0
		rem = 0
		for i in range(t, len(s)):
			rem = 2 * rem
			rem += int(s[i] == '1')
			if rem == 2 or rem == 1:
				continue
			cars = i - t + 1
			req = rem - cars
			if cnt < req:
				break
			total += 1
	print(total)


T = int(input())
d = dict()
num = int(2 * 100000.0 + 11)
for t in range(T):
	s = input()
	n = len(s)
	stack = set()
	tr = 0
	for i in range(n):
		if s[i] == '1':
			stack.add(i)
			break
	d_trail = dict()
	for i in range(n):
		if s[i] == '0':
			tr += 1
		else:
			d_trail[i] = tr
			tr = 0
			stack.add(i)
	ans = 0
	ct = 0
	while stack:
		ct += 1
		k = stack.pop()
		for i in range(k + 1, min(k + 35, n)):
			if int(s[k:i + 1], 2) == i - k + 1:
				ans += 1
			if int(s[k:i + 1], 2) > i - k + 1:
				if int(s[k:i + 1], 2) <= i + 1 - k + d_trail[k]:
					ans += 1
	print(ans + s.count('1'))


import sys
stdin = sys.stdin
test_case = int(stdin.readline())
while test_case:
	test_case -= 1
	s = stdin.readline().rstrip()
	nxt_one = [0] * len(s)
	nxt_one[0] = -1
	tmp = -1 if s[0] == '0' else 0
	for i in range(1, len(s)):
		nxt_one[i] = tmp
		if s[i] == '1':
			tmp = i
	ans = 0
	for i in range(len(s)):
		cur = 0
		new_one = nxt_one[i] if s[i] == '0' else i
		while i - new_one < 18 and new_one != -1:
			cur |= 1 << i - new_one
			if cur <= i - nxt_one[new_one]:
				ans += 1
			new_one = nxt_one[new_one]
	print(ans)


from sys import stdin, stdout
t = int(stdin.readline())
for _ in range(t):
	s = stdin.readline()
	s = s[:-1]
	n = len(s)
	precomp = []
	for i in range(len(s)):
		if i == 0 and s[i] == '0':
			precomp.append(-1)
		elif s[i] == '1':
			precomp.append(i)
		else:
			precomp.append(precomp[-1])
	l = 0
	r = 0
	count = 0
	while r < n:
		l = r
		sum1 = 0
		while l >= 0 and r - l < 20:
			if s[l] != '0':
				sum1 += 1 << r - l
				if sum1 == r - l + 1:
					count += 1
				if sum1 > r - l + 1:
					dif = sum1 - r + l - 1
					ls = l - dif
					rs = ls + dif - 1
					if ls >= 0 and rs <= n - 1 and (s[ls] == '0') and (s[rs] == '0') and (precomp[ls] == precomp[rs]):
						count += 1
			l -= 1
		r += 1
	stdout.write(str(count) + '\n')


import sys

def input():
	return sys.stdin.readline().rstrip()

def slv():
	s = list(input()[::-1])
	s = list(map(int, s))
	ans = 0
	n = len(s)
	RPOS = [n] * n
	for i in range(n):
		if s[i] == 1:
			RPOS[i] = i
	for i in range(n - 1, -1, -1):
		if i + 1 < n:
			RPOS[i] = min(RPOS[i], RPOS[i + 1])
	for l in range(n):
		(left_comp, right_comp) = (0, 0)
		for r in range(l, min(l + 20, n)):
			left_comp += pow(2, r - l) * s[r]
			right_comp += 1
			if left_comp == right_comp:
				ans += 1
		m = min(l + 20, n) - 1
		if right_comp < left_comp <= RPOS[m] - l:
			ans += 1
	print(ans)
	return

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

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


t = int(input())
for _ in range(t):
	s = [int(x) for x in input()]
	next1 = [0 for _ in range(len(s))]
	idx1 = -1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 1:
			idx1 = i
		next1[i] = idx1
	c = 0
	for i in range(len(s)):
		val = 0
		if next1[i] < 0:
			continue
		for j in range(next1[i], min(next1[i] + 20, len(s))):
			val = val * 2 + s[j]
			if val == j - i + 1:
				c += 1
	print(c)


for t in range(int(input())):
	sinp = input()
	subs = 0
	for l in range(1, min(20, len(sinp)) + 1):
		pz = 0
		for i in range(len(sinp) - l + 1):
			if sinp[i] == '0':
				pz += 1
				continue
			binx = int(sinp[i:i + l], 2)
			if binx >= l and binx - l <= pz:
				subs += 1
			pz = 0
	print(subs)


import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
t = I()
for _ in range(t):
	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 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)):
				if i + len(strings[j]) - 1 <= len(s) - 1:
					if s[i:i + len(strings[j])] == strings[j]:
						ans += 1
			z = 0
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
for _ in range(int(input())):
	s = input()
	n = len(s)
	a = [0] * n
	l = 0
	for i in range(n):
		if s[i] == '0':
			l += 1
		a[i] = l
		if s[i] == '1':
			l = 0
	ans = 0
	for i in range(n):
		if s[i] == '1':
			t = ''
			for j in range(i, min(n, i + 20)):
				t += s[j]
				if int(t, 2) <= j - i + 1 + a[i]:
					ans += 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	s = input().rstrip()
	ans = zeroes = 0
	n = len(s)
	for i in range(n):
		if s[i] == '0':
			zeroes += 1
		else:
			for j in range(1, min(19, n - i + 1)):
				k = int(s[i:i + j], 2)
				if zeroes + j >= k:
					ans += 1
				else:
					continue
			zeroes = 0
	print(ans)


import sys
input = sys.stdin.readline

def getInt():
	return int(input())

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

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

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

def addDictList(d, key, val):
	if key not in d:
		d[key] = []
	d[key].append(val)

def addDictInt(d, key, val):
	if key not in d:
		d[key] = 0
	d[key] = val

def addDictCount(d, key):
	if key not in d:
		d[key] = 0
	d[key] += 1

def addDictSum(d, key, val):
	if key not in d:
		d[key] = 0
	d[key] += val

def max0(s):
	m1 = 1
	m2 = len(s)
	while m2 - m1 > 5:
		m3 = (m1 + m2) // 2
		p = s.find('0' * m3)
		if p > -1:
			m1 = m3
		else:
			m2 = m3
	res = 0
	for i in range(m1, m2):
		p = s.find('0' * i)
		if p > -1:
			res = i
		else:
			break
	return res
t = getInt()
for _ in range(t):
	s = getStr()
	res = 0
	d = {}
	d1 = []
	for i in range(len(s)):
		if s[i] == '1':
			d1.append(i)
	d['1'] = d1
	res += len(d1)
	while len(d) > 0:
		(key, val) = d.popitem()
		(d0, d1) = ([], [])
		p1 = len(key) - 1
		p2 = p1 + 1
		for p in val:
			if p + len(key) >= len(s):
				continue
			if s[p + len(key)] == '0':
				if p >= p1 and s[p - p1:p] == '0' * p1:
					d0.append(p - p1)
			elif p >= p2 and s[p - p2:p] == '0' * p2:
				d1.append(p - p2)
		res += len(d0)
		res += len(d1)
		if len(d0) > 0:
			d['0' * p1 + key + '0'] = d0
		if len(d1) > 0:
			d['0' * p2 + key + '1'] = d1
	print(res)


n = int(input())
for _ in range(n):
	s = input()
	ans = 0
	zeros = 0
	for i in range(len(s)):
		if s[i] == '1':
			for j in range(1, 19):
				if i + j > len(s):
					continue
				a = s[i:i + j]
				f = int(a, 2)
				if zeros + j >= f:
					ans += 1
			zeros = 0
		else:
			zeros += 1
	print(ans)


occur1 = []
large = 150000

def count(a, b):
	ret = occur1[b]
	if a - 1 >= 0:
		ret -= occur1[a - 1]
	return ret

def findcount(st, s):
	ssum = 0
	po = 1
	ans = 0
	for i in range(s, min(s + 20, len(st))):
		if st[i] == '1':
			ssum += po
		po *= 2
		if ssum == i - s + 1:
			ans += 1
	end = min(s + 20, len(st))
	if s + 20 < len(st) and ssum > 20:
		need1 = s + 20
		need2 = s + ssum - 1
		if need2 < len(st) and count(need1, need2) == 0:
			ans += 1
	return ans

def solve():
	s = input()
	s = s[::-1]
	occur1.clear()
	for i in range(len(s)):
		if s[i] == '1':
			occur1.append(1)
		else:
			occur1.append(0)
	for i in range(1, len(occur1)):
		occur1[i] += occur1[i - 1]
	ans = 0
	for i in range(0, len(s)):
		ans += findcount(s, i)
	print(ans)

def main():
	test = eval(input())
	for t in range(test):
		solve()
main()


t = int(input())
for _ in range(t):
	A = input()
	zeroes = 0
	result = 0
	for i in range(len(A)):
		if A[i] == '0':
			zeroes += 1
		else:
			j = 0
			while 1 << j <= len(A) and i + j + 1 <= len(A):
				a = int(A[i:i + j + 1], 2)
				if j + 1 <= a and a <= j + 1 + zeroes:
					result += 1
				j += 1
			zeroes = 0
	print(result)


from collections import defaultdict
import sys
import bisect
input = sys.stdin.readline
t = int(input())
for ii in range(t):
	s = input()
	s = s[:len(s) - 1]
	ans = 0
	dec = 0
	ok = False
	for i in range(len(s)):
		if s[i] == '0':
			dec += 1
		else:
			for j in range(i + 1, len(s) + 1):
				bina = int(s[i:j], 2)
				if dec + j - i < bina:
					break
				ans += 1
			dec = 0
	print(ans)


import sys, time
from os import path
from collections import *
from heapq import *
from math import *

def solve(kkkk):
	s = ins()
	n = len(s)
	ans = 0
	lef = crarr(0, n)
	for i in range(0, n - 1):
		if s[i] == '0':
			lef[i + 1] = 1 + lef[i]
	for i in range(n):
		if s[i] == '0':
			continue
		j = i
		val = 0
		while j < n and 2 * val <= n:
			val *= 2
			val += int(s[j])
			lb = j - i + 1
			rb = lef[i] + lb
			if val >= lb and val <= rb:
				ans += 1
			j += 1
	out(ans)

def main():
	t = 1
	t = inp()
	for i in range(t):
		solve(i + 1)
localsys = 0
start_time = time.time()
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	localsys = 1
cin = sys.stdin.readline
cout = sys.stdout.write

def inp():
	return int(cin().strip())

def ins():
	return list(cin().strip())

def inm():
	return map(int, cin().strip().split())

def ina():
	return list(map(int, cin().strip().split()))

def out(a):
	cout(str(a) + '\n')

def outa(a):
	cout(' '.join(map(str, a)) + '\n')

def outm(a, b, c=None, d=None):
	cout(str(a) + ' ' + str(b))
	if c != None:
		cout(' ' + str(c))
	if d != None:
		cout(' ' + str(d))
	cout('\n')

def crarr(a, n):
	return [a for i in range(n)]
main()
if localsys:
	print('\n\nTime Elapsed :', time.time() - start_time, 'seconds')


import sys
t = int(input())
for _ in range(t):
	s: str = '*' + sys.stdin.readline().rstrip() + '*'
	n = len(s)
	zero = [0] * n
	p = []
	for i in range(1, n):
		if s[i] == '0':
			zero[i] = zero[i - 1] + 1
		else:
			zero[i] = 0
		if s[i] == '1':
			p.append(i)
	ans = s.count('1') + s.count('10') + s.count('011')
	for j in p:
		for k in range(4, n):
			target = bin(k)[2:]
			leading_zero = k - len(target)
			suf = len(target)
			if leading_zero > zero[j - 1]:
				break
			if target == s[j:j + suf]:
				ans += 1
	print(ans)


for __ in range(int(input())):
	s = input()
	a = [0] * len(s)
	for i in range(1, len(s)):
		if s[i - 1] == '0':
			a[i] = a[i - 1] + 1
		else:
			a[i] = 0
	ans = 0
	for i in range(len(s)):
		if s[i] == '1':
			t = 1
			ans += 1
			for j in range(i + 1, min(len(s), i + 18)):
				if s[j] == '1':
					t = t * 2 + 1
				else:
					t = t * 2
				if a[i] >= t - (j - i + 1):
					ans += 1
	print(ans)


import sys
input = sys.stdin.readline
al = []

def solve():
	global al
	cur = input()
	n = len(cur)
	cnt = ans = 0
	for i in range(n):
		if cur[i] == '0':
			cnt += 1
			continue
		val = 0
		while cnt + 17 >= al[val]:
			val += 1
		for j in range(val):
			if i + j + 1 >= n:
				break
			if int(cur[i:i + j + 1], 2) <= cnt + j + 1:
				ans += 1
		cnt = 0
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
al.append(0)
cur = 1
while cur < 1000000:
	al.append(cur)
	cur *= 2
main()


for _ in range(int(input())):
	s = input()
	L = len(s)
	NOZBT = []
	cnt = 0
	ans = 0
	for i in s:
		NOZBT.append(cnt)
		if i == '0':
			cnt += 1
		else:
			cnt = 0
	for i in range(L):
		v = 0
		if s[i] == '1':
			for j in range(i, min(i + 18, L)):
				v = (v << 1) + int(s[j])
				if NOZBT[i] >= v - j + i - 1:
					ans += 1
	print(ans)


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)


for _ in range(int(input())):
	s = input()
	ans = 0
	p = 0
	for i in range(len(s)):
		if s[i] == '0':
			p += 1
			continue
		ans += 1
		a1 = 1
		a2 = 1
		for j in range(i + 1, min(i + 19, len(s))):
			a2 += 1
			a1 *= 2
			a1 += s[j] == '1'
			ans += a1 >= a2 and a1 <= p + a2
		p = 0
	print(ans)


def main():
	T = int(input().strip())
	for case in range(T):
		(ans, cur) = (0, 0)
		s = input().strip()
		lens = len(s)
		for i in range(lens):
			if s[i] == '0':
				cur += 1
				continue
			num = 0
			for j in range(i, lens):
				if s[j] == '1':
					num = num * 2 + 1
				else:
					num = num * 2
				if cur >= num - j + i - 1:
					ans += 1
				else:
					break
			cur = 0
		print(ans)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def pre(s):
	n = len(s)
	pi = [0] * n
	for i in range(1, n):
		j = pi[i - 1]
		while j and s[i] != s[j]:
			j = pi[j - 1]
		if s[i] == s[j]:
			j += 1
		pi[i] = j
	return pi

def prod(a):
	ans = 1
	for each in a:
		ans = ans * each
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)
from math import inf
from collections import deque

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	s = input()
	n = len(s)
	zero = 0
	ans = 0
	for i in range(n):
		if s[i] == '0':
			zero += 1
			continue
		j = i
		while j < n:
			cur = int(s[i:j + 1], 2)
			if zero + j - i + 1 >= cur:
				ans += 1
				j += 1
			else:
				break
		zero = 0
	print(ans)


def read_int():
	return int(input())

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

def solve(s: str) -> int:
	ones = []
	for (i, num) in enumerate(s):
		if num == '1':
			ones.append(i)
	ans = 0
	for (s_iter, letter) in enumerate(s):
		current_val = 0
		if letter == '1':
			ones.pop(0)
			current_len = 1
			t_iter = s_iter
		else:
			if len(ones) <= 0:
				return ans
			next_one = ones[0]
			current_len = next_one - s_iter + 1
			t_iter = next_one
		while t_iter < len(s) and current_val <= current_len:
			current_val = 2 * current_val + int(s[t_iter])
			if current_val == current_len:
				ans += 1
			t_iter += 1
			current_len += 1
	return ans
t = read_int()
for _ in range(t):
	print(solve(input()))


try:
	from string_source import string_source
	source = string_source('4\n0110\n0101\n00001000\n0001000')
except ImportError:
	source = input
import math

def get_leading_zeros(n):
	bit_size = int(math.log2(n) + 1)
	return n - bit_size
ZEROS = {}
for i in reversed(range(2, int(200000.0))):
	ZEROS[get_leading_zeros(i)] = '{0:b}'.format(i)[::-1]

def check_string(s):
	s = list(map(int, reversed(s)))
	dp = [0] * len(s)
	dp[0] = s[0]
	zeros_seen = 0
	idx = 1
	while idx < len(s):
		if s[idx] == 1:
			zeros_seen = 0
		else:
			zeros_seen += 1
		dp[idx] = dp[idx - 1]
		dp[idx] += s[idx]
		tt = ZEROS[zeros_seen]
		dp[idx] += ''.join(map(str, s[max(0, idx - zeros_seen - len(tt) + 1):idx - zeros_seen + 1])) == tt
		if all((t == '1' for t in tt)):
			tt = '0' * len(tt) + '1'
			dp[idx] += ''.join(map(str, s[max(0, idx - zeros_seen - len(tt) + 1):idx - zeros_seen + 1])) == tt
		idx += 1
	return dp[-1]
t = int(source())
for _ in range(t):
	print(check_string(source()))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math
import bisect
for j in range(int(input())):
	vals = [k for k in input()]
	tracker = []
	power = math.ceil(math.log2(len(vals)))
	for s in range(len(vals)):
		if vals[s] == '1':
			tracker.append(s)
	ans = 0
	for s in range(len(tracker)):
		ind0 = tracker[s]
		if s >= 1:
			ind1 = tracker[s - 1] + 1
		else:
			ind1 = 0
		zeros = ind0 - ind1
		str1 = ''
		for b in range(ind0, min(ind0 + power + 1, len(vals))):
			if vals[b] == '1':
				str1 += '1'
			else:
				str1 += '0'
			if int(str1, 2) <= zeros + len(str1):
				ans += 1
	print(ans)


import math
for T_T in range(int(input())):
	s = input()
	sLen = len(s)
	leftZero = list(range(sLen + 3))
	for i in range(sLen):
		if s[i] == '0':
			if leftZero[i] == 0:
				leftZero[i + 1] = 1
			else:
				leftZero[i + 1] = leftZero[i] + 1
		else:
			leftZero[i + 1] = 0
	ans = 0
	for nowLen in range(min(20, int(math.log2(sLen)) + 1)):
		nowValue = int(0)
		andValue = (1 << nowLen + 1) - 1
		for i in range(sLen):
			nowValue <<= 1
			nowValue &= andValue
			nowValue |= s[i] == '1'
			if i >= nowLen and s[i - nowLen] == '1' and (leftZero[i - nowLen] >= nowValue - int(math.log2(nowValue)) - 1):
				ans = ans + 1
	print(ans)


for _ in range(int(input())):
	s = input()
	a = [-1] + [i for (i, j) in enumerate(s) if j == '1']
	ans = 0
	for (i, v) in enumerate(a[1:], 1):
		ans += 1
		val = 1
		for j in range(v + 1, len(s)):
			val = (val << 1) + (s[j] == '1')
			if val - (j - v + 1) <= v - a[i - 1] - 1:
				ans += 1
			else:
				break
	print(ans)


import math
t = int(input())
for _ in range(t):
	item = tuple((int(x) for x in input()))
	(count, zn, n) = (0, 0, len(item))
	lg = int(math.log2(n)) + 1
	for s in range(n):
		if item[s] == 0:
			zn += 1
			continue
		_sum = 0
		for j in range(s, min(s + lg, n)):
			_sum += item[j]
			length = j - s + 1
			if _sum == length or (_sum <= length + zn and _sum > length):
				count += 1
			_sum = _sum * 2
		zn = 0
	print(count)


t = int(input())
while t > 0:
	s = input()
	good = 0
	length = 0
	for i in range(0, len(s)):
		if s[i] == '0':
			length += 1
		else:
			f = 0
			for j in range(i, len(s)):
				length += 1
				f = (f << 1) + int(s[j])
				if f > length:
					break
				good += 1
			length = 0
	print(good)
	t -= 1


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
				if zeros >= k - j:
					ANS += 1
			zeros = 0
	print(ANS)


def main():
	import sys
	input = sys.stdin.readline
	for _ in range(int(input())):
		S = input().rstrip('\n')
		N = len(S)
		cnt = 0
		ans = 0
		for (i, s) in enumerate(S):
			if s == '0':
				cnt += 1
			else:
				j = 0
				f = 0
				while True:
					f *= 2
					f += int(S[i + j])
					if f - (j + 1) <= cnt:
						ans += 1
					else:
						break
					j += 1
					if i + j == N:
						break
				cnt = 0
		print(ans)
main()


for _ in range(int(input())):
	l = input()
	n = len(l)
	(zeros, cnt) = (0, 0)
	for i in range(n):
		if l[i] == '0':
			zeros += 1
		else:
			for j in range(i, n):
				if zeros + (j - i + 1) >= int(l[i:j + 1], 2):
					cnt += 1
				else:
					break
			zeros = 0
	print(cnt)


for _ in range(int(input())):
	s = [int(x) for x in list(input().strip())]
	n = len(s)
	an = 0
	c = 0
	for i in range(n):
		if s[i] == 1:
			p = 0
			for j in range(18):
				if i + j == n:
					break
				else:
					p = p << 1
					p += s[i + j]
					if p >= j + 1 and p <= j + 1 + c:
						an += 1
			c = 0
		else:
			c += 1
	print(an)


t = int(input())
for _ in range(t):
	s = input()
	cnt = 0
	for l in range(1, 19):
		lead = 0
		val = 0
		for i in range(len(s)):
			d = int(s[i])
			if i <= l - 1:
				val += d * 2 ** (l - i - 1)
			else:
				d2 = int(s[i - l])
				val -= d2 * 2 ** (l - 1)
				val *= 2
				val += d
				if d2 == 0:
					lead += 1
				else:
					lead = 0
			if i >= l - 1 and s[i - l + 1] == '1' and (lead + l >= val):
				cnt += 1
	print(cnt)


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)


t = int(input())
for i in range(t):
	s = [int(i) for i in list(input())]
	id_now = -1
	right_nearest = [-1] * len(s)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == 1:
			id_now = i
		right_nearest[i] = id_now
	ans = 0
	for i in range(len(s)):
		if s[i] == 1:
			ans += 1
			if i != len(s) - 1:
				if s[i + 1] == 0:
					ans += 1
		elif right_nearest[i] < 0:
			continue
		else:
			s_now = 0
			for j in range(right_nearest[i], min(right_nearest[i] + 20, len(s))):
				s_now = 2 * s_now + s[j]
				if s_now == j - i + 1:
					ans += 1
	print(ans)


import sys
input = sys.stdin.readline
from math import *
for _ in range(int(input())):
	s = input().rstrip()
	n = len(s)
	a = [0] * n
	ll = []
	for i in range(1, n):
		a[i] = a[i - 1] + 1 if s[i - 1] == '0' else 0
	for i in range(n):
		if s[i] == '1':
			ll.append(i)
	ans = 0
	for i in ll:
		lo = i
		nn = 1
		while (1 << nn - 1) - nn <= a[i]:
			nn += 1
		hi = min(n, lo + nn + 1)
		while lo + 1 < hi:
			mid = (lo + hi) // 2
			if int(s[i:mid + 1], 2) - (mid - i + 1) > a[i]:
				hi = mid
			else:
				lo = mid
		ans += lo - i + 1
	print(ans)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

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

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 998244353
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(ii()):
		s = si()
		n = len(s)
		ans = 0
		c = 0
		for i in range(n):
			if s[i] == '1':
				x = 1
				ans += 1
				for j in range(min(c + 1, n - i - 1)):
					x *= 2
					if s[i + j + 1] == '1':
						x += 1
					if j + 2 + c >= x:
						ans += 1
					else:
						break
				c = 0
			else:
				c += 1
		print(ans)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


t = int(input())
for _ in range(t):
	s = input()
	zeros = [0] * len(s)
	for i in range(len(s)):
		if s[i] == '0':
			zeros[i] = (zeros[i - 1] if i > 0 else 0) + 1
	res = 0
	for i in range(len(s)):
		cur = 0
		for j in range(19):
			if i - j < 0:
				break
			if s[i - j] == '1':
				cur += 2 ** j
			if s[i - j] == '1' and (cur == j + 1 or (i - j > 0 and zeros[i - j - 1] + j + 1 >= cur)):
				res += 1
	print(res)


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)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	s = input()
	n = len(s)
	prev = 0
	ans = 0
	dp = [-1] * (n + 1)
	se = set()
	for i in range(n):
		if s[i] == '1':
			dp[i + 1] = i
		else:
			dp[i + 1] = dp[i]
	for i in range(n):
		for j in range(i + 1, min(n + 1, i + 19)):
			e = s[i:j]
			y = int(e, 2)
			if len(e) == y:
				if (i, j) not in se:
					ans += 1
					se.add((i, j))
			elif y > 18:
				if y <= len(e) + i - dp[i] - 1:
					ser = j - y + 1
					if (ser, j) not in se:
						ans += 1
						se.add((ser, j))
	print(ans)


import sys

def rint():
	return map(int, sys.stdin.readline().split())
num_table = set()
for i in range(2 * 10 ** 5):
	pre_zero = i - (len(bin(i)) - 2)
	bin_str = bin(i)[2:]
	num_table.add((pre_zero, bin_str))
t = int(input())
for tt in range(t):
	s = input()
	pre_z = []
	z_cnt = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			z_cnt += 1
		else:
			z_cnt = 0
		pre_z.append(z_cnt)
	pre_z.reverse()
	ans = 0
	for j in range(len(s)):
		pz = pre_z[j]
		for k in range(1 + 19):
			if j + pz + k > len(s):
				break
			if (pz, s[j + pz:j + pz + k]) in num_table:
				ans += 1
	print(ans)


import sys
inf = 2 * 10 ** 5
inf_bin = len(bin(inf)[2:])

def pre_calculate_amount_of_zero_left(s):
	prefix = [0] * len(s)
	cur_amount = 0
	for i in range(0, len(s)):
		if s[i] == '0':
			cur_amount += 1
		elif s[i] == '1':
			prefix[i] = cur_amount
			cur_amount = 0
	return prefix

def solve_for_bit_len(string, pref, bit_len):
	ans = 0
	for i in range(0, len(string) - bit_len + 1):
		if string[i] == '1':
			num = int(string[i:i + bit_len], 2)
			rem = num - bit_len
			if num <= inf and rem <= pref[i]:
				ans += 1
	return ans
for q in range(0, int(sys.stdin.readline().strip())):
	s = str(sys.stdin.readline().strip())
	amount_of_zero_left = pre_calculate_amount_of_zero_left(s)
	ans = 0
	for bit_len in range(1, inf_bin + 1):
		ans += int(solve_for_bit_len(s, amount_of_zero_left, bit_len))
	print(ans)


R = lambda : map(int, input().split())
for _ in range(int(input())):
	s = [i for i in input()]
	l = len(s)
	L = [0 for i in range(l)]
	c = 0
	for i in range(l):
		if s[i] == '1':
			L[i] = c
			c = 0
		else:
			c += 1
	i = l - 1
	res = 0
	while i >= 0:
		if s[i] == '1':
			k = min(l, i + 20)
			t = '0b' + ''.join(s[i:k])
			v = int(t, 2)
			p = k - i
			while p > 0:
				if p + L[i] >= v:
					res += 1
				v >>= 1
				p -= 1
		i -= 1
	print(res)


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':
						tot += aa[ii]
				le = tot - i
				try:
					xx = ss[j - 1]
					if j - xx >= le:
						ans += 1
				except:
					if le == 0:
						ans += 1
					pass
	print(ans)


def find(s):
	powers = {}
	for i in range(30):
		powers[i] = 2 ** i
	s_rev = s[::-1]
	zeros = [0] * len(s)
	cur = 0
	for i in range(len(s)):
		if s[i] == '0':
			cur += 1
		else:
			cur = 0
		zeros[i] = cur
	zeros = zeros[::-1]
	count = 0
	for i in range(len(s)):
		if s[i] == '1':
			count += 1
	for i in range(len(s_rev)):
		if s_rev[i] == '1':
			temp = int(s_rev[i])
			if i == len(s_rev) - 1:
				reminding_zeros = 0
			else:
				reminding_zeros = zeros[i + 1]
			for j in range(1, 19):
				if i - j < 0:
					break
				temp *= 2
				temp += int(s_rev[i - j])
				if reminding_zeros >= temp - (j + 1):
					count += 1
	return count
for _ in range(int(input())):
	print(find(input()))


from collections import deque
(t, *s) = open(0).read().split()
for x in s:
	l = len(x)
	zero = 0
	ans = 0
	for i in range(l):
		if x[i] == '0':
			zero += 1
		else:
			ans += 1
			temp = 1
			for j in range(1, min(17, l - i - 1) + 1):
				if x[i + j] == '0':
					temp = temp << 1
				else:
					temp = (temp << 1) + 1
				if zero < temp - temp.bit_length():
					break
				else:
					ans += 1
			zero = 0
	print(ans)