Prof. Twotwo as the name suggests is very fond powers of 2. Moreover he also has special affinity to number 800. He is known for carrying quirky experiments on powers of 2.

One day he played a game in his class. He brought some number plates on each of which a digit from 0 to 9 is written. He made students stand in a row and gave a number plate to each of the student. Now turn by turn, he called for some students who are standing continuously in the row say from index i to index j (i<=j) and asked them to find their strength.

The strength of the group of students from i to j is defined as:

strength(i , j)
{
    if a[i] = 0
        return 0; //If first child has value 0 in the group, strength of group is zero
    value = 0;
    for k from i to j
        value = value*10 + a[k]
    return value;
} 

Prof called for all possible combinations of i and j and noted down the strength of each group. Now being interested in powers of 2, he wants to find out how many strengths are powers of two. Now its your responsibility to get the answer for prof.

Input Format

First line contains number of test cases T 

Next T line contains the numbers of number plates the students were having when standing in the row in the form of a string A.

Constraints

1 ≤ T ≤ 100 

1 ≤ len(A) ≤ $10^{5}$ 

0 ≤ A[i] ≤ 9

Output Format

Output the total number of strengths of the form 2^{x} such that 0 ≤ x ≤ 800. 

Sample Input 0
5
2222222
24256
65536
023223
33579

Sample Output 0
7
4
1
4
0

Explanation 0

In following explanations group i-j is group of student from index i to index j (1-based indexing)

In first case only 2 is of form power of two. It is present seven times for groups 1-1,2-2,3-3,4-4,5-5,6-6,7-7  

In second case 2,4 and 256 are of required form. 2 is strength of group 1-1 and 3-3, 4 is strength of group 2-2 and 256 is strength of group 3-5.

In third case 65536 is only number in required form. It is strength of group 1-5

In fourth case 2 and 32 are of forms power of 2. Group 1-2 has values 0,2 but its strength is 0, as first value is 0.  

In fifth case, None of the group has strength of required form.

Source: hackerrank | Difficulty: HARD
Tags: String algorithms


Solutions:
tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


from collections import deque
import os

class Node:

	def __init__(self, value, fail=None):
		self.value = value
		self.count = 0
		self.leafs = {}
		if fail == None:
			self.fail = self
		else:
			self.fail = fail

	def create_and_return_leaf(self, value):
		if value not in self.leafs:
			self.leafs[value] = Node(value, self.fail)
		return self.leafs[value]

	def find_fail(self, value):
		fail = self.fail
		while value not in fail.leafs:
			fail = fail.fail
		return fail.leafs[value]

	def next_leaf(self, value):
		if value in self.leafs:
			return self.leafs[value]
		return self.find_fail(value)
mx = 2 ** 800
twos_tree = {}
ct = 1
root = Node(None)
while ct <= mx:
	digits = 0
	tmp = ct
	while tmp >= 10:
		digits += 1
		tmp //= 10
	node = root
	while digits >= 0:
		digit = ct // 10 ** digits % 10
		node = node.create_and_return_leaf(digit)
		digits -= 1
	node.count += 1
	ct *= 2
queue = deque(root.leafs.values())
for k in range(10):
	if k in root.leafs:
		continue
	root.leafs[k] = root
while len(queue) > 0:
	cur = queue.popleft()
	for leaf in cur.leafs.values():
		queue.append(leaf)
		fail = cur.find_fail(leaf.value)
		leaf.fail = fail
		leaf.count += leaf.fail.count
base = ord('0')
n = int(input())
c = 0
while c < n:
	c += 1
	count = 0
	node = root
	for digit in input():
		node = node.next_leaf(ord(digit) - base)
		count += node.count
	print(count)


import string

class Trie:

	def __init__(self, s_id=None):
		self.s_id = s_id
		self.edges = {}
		self.err_f = None
		self.out = set()
		if self.s_id is not None:
			out.add(self.s_id)
		self.out_l = len(self.out)

	def add_s(self, s, s_id):
		if len(s) == 0:
			self.s_id = s_id
			self.out.add(s_id)
			self.out_l = len(self.out)
			return
		c1 = s[0]
		cn = s[1:]
		if c1 not in self.edges:
			self.edges[c1] = Trie()
		self.edges[c1].add_s(cn, s_id)

	def match(self, s):
		if len(s) == 0:
			return self.s_id is not None
		c1 = s[0]
		cn = s[1:]
		if c1 in self.edges:
			return self.edges[c1].match(cn)
		else:
			return False

	def ac_match(self, s):
		count = 0
		q = self
		for c in s:
			while c not in q.edges and q is not self:
				q = q.err_f
			if q is self and c not in q.edges:
				continue
			q = q.edges[c]
			count += q.out_l
		return count
n = int(input())
graph = Trie()
for i in range(801):
	graph.add_s(str(2 ** i), i)
q = []
graph.err_f = graph
for a in graph.edges:
	graph.edges[a].err_f = graph
	q.append(graph.edges[a])
while len(q) > 0:
	r = q.pop(0)
	for a in r.edges:
		q.append(r.edges[a])
		v = r.err_f
		while v is not graph and a not in v.edges:
			v = v.err_f
		u = r.edges[a]
		if a not in v.edges:
			u.err_f = graph
		else:
			u.err_f = v.edges[a]
		u.out = u.out | u.err_f.out
		u.out_l = len(u.out)
for x in range(n):
	s = input().strip()
	print(graph.ac_match(s))


def hr():
	number_of_tests = int(input())
	for i in range(number_of_tests):
		number = input().strip()
		print(calculate_optimised2(number))

def prefill2():
	previous = 1
	numbersOfExtent2 = ['1']
	for i in range(1, 801):
		current = previous * 2
		numbersOfExtent2.append(str(current))
		previous = current
	final = {}
	for number in numbersOfExtent2:
		if len(number) < 5:
			final[number] = [number]
		elif number[:5] in final:
			final[number[:5]].append(number)
		else:
			final[number[:5]] = [number]
	return final

def calculate_optimised2(number):
	calculated_powers_of_2 = prefill2()
	total = 0
	post_calculated = {}
	i = 0
	while i < len(number):
		if number[i] == '0':
			i += 1
			continue
		number_for_comparising = number[i:i + 5]
		prefix = number_for_comparising[:4]
		if not prefix in post_calculated:
			current_string = ''
			current_total = 0
			for j in prefix:
				current_string += j
				if current_string in calculated_powers_of_2:
					current_total += 1
			post_calculated[prefix] = current_total
			total += current_total
		else:
			total += post_calculated[prefix]
		if len(number_for_comparising) > 4 and number_for_comparising[:5] in calculated_powers_of_2:
			for number_of_extent_2 in calculated_powers_of_2[number_for_comparising[:5]]:
				if number[i:].startswith(number_of_extent_2):
					total += 1
		i += 1
	return total
hr()


from collections import deque
import sys

class Node(object):

	def __init__(self):
		self.goto = [None for i in range(10)]
		self.fail = None
		self.out = set()

def build_trie(root, alternatives, prefix=()):
	previous = None
	followers = []
	for s in alternatives:
		if not s:
			root.out.add(prefix)
		elif s[0] == previous:
			followers.append(s[1:])
		else:
			if previous is not None:
				root.goto[previous] = build_trie(Node(), followers, prefix + (previous,))
			previous = s[0]
			followers = [s[1:]]
	if previous is not None:
		root.goto[previous] = build_trie(Node(), followers, prefix + (previous,))
	return root

def build_automaton(root, alternatives):
	alphabet = range(len(root.goto))
	for symbol in alphabet:
		root.goto[symbol] = root
	build_trie(root, alternatives)
	queue = deque()
	for symbol in alphabet:
		node = root.goto[symbol]
		if node is not root:
			node.fail = root
			queue.append(node)
	while queue:
		node = queue.popleft()
		for symbol in alphabet:
			child = node.goto[symbol]
			if child is not None:
				queue.append(child)
				v = node.fail
				while v.goto[symbol] is None:
					v = v.fail
				child.fail = v.goto[symbol]
				child.out |= child.fail.out
	return root
automaton = build_automaton(Node(), sorted(([int(digit) for digit in str(2 ** i)] for i in range(801))))

def count_groups(digits):
	count = 0
	node = automaton
	for symbol in digits:
		while node.goto[symbol] is None:
			node = node.fail
		node = node.goto[symbol]
		count += len(node.out)
	return count
t = int(next(sys.stdin).strip())
for i in range(t):
	print(count_groups([int(digit) for digit in next(sys.stdin).strip()]))


from collections import OrderedDict
import time

def ti():
	return time.time()

def profile(s, sort=1):
	import cProfile
	cProfile.run(s, sort=sort)
from functools import wraps
import inspect

def initializer(fun):
	(names, varargs, keywords, defaults) = inspect.getargspec(fun)

	@wraps(fun)
	def wrapper(self, *args, **kargs):
		for (name, arg) in list(zip(names[1:], args)) + list(kargs.items()):
			setattr(self, name, arg)
		if defaults:
			for i in range(len(defaults)):
				index = -(i + 1)
				if not hasattr(self, names[index]):
					setattr(self, names[index], defaults[index])
		fun(self, *args, **kargs)
	return wrapper

def tel(n=5):
	return [i + 1 for i in range(n)]

def tel2(n=4, m=None):
	if m == None:
		m = n
	return [[i * m + j + 1 for j in range(m)] for i in range(n)]

def tels(n=5):
	return 'abcde' * 2

def abc(n):
	return list(map(chr, range(97, 123)))[n]

def lflat2(l):
	if ist(l[0], list):
		return [x for y in l for x in y]
	else:
		return l

def lflat(l):
	return lflat2(l)

def lflat(l):
	nl = []
	for x in l:
		if type(x) == list:
			nl += lflat(x)
		else:
			nl.append(x)
	return nl

def ist(o, t):
	return isinstance(o, t)

def lm(f, *l):
	return list(map(f, *l))
n = 2 ** 800
dn = OrderedDict()
for power in range(0, 801):
	n = str(2 ** power)
	dn[n] = sum([n.count(x) for x in dn]) + 1
l = list(dn)

def powcount(s):
	su = 0
	le = len(s)
	for x in l:
		su += s.count(x)
		if len(x) > le:
			break
	return su

class Node(dict):

	@initializer
	def __init__(self, par=None, c=None):
		self.depo = []
		self.bros = []
		self.end = False

def addpath(t, s):
	for x in s:
		if x not in t:
			t[x] = Node(t, x)
		t = t[x]
	t.end = True
	t.path = s
	t.pos = len(s) - 1
	t.depo += [t.pos]

def getpath(t, root):
	s = ''
	while t.par:
		s += t.c
		t = t.par
	return s[::-1]

def chartree(l):
	t = Node()
	for x in l:
		addpath(t, x)
	return t

def addbros(root, t):
	for c in t:
		node = t[c]
		if t != root:
			node.bros = [x[c] for x in node.par.bros if c in x]
			if c in root:
				node.bros += [root[c]]
			node.depo += [x.pos for x in node.bros if x.end]
		addbros(root, node)
	return root

def railtree(l):
	root = chartree(l)
	return addbros(root, root)

def nextmove(t, c, root):
	if c in t:
		t = t[c]
	else:
		nobros = True
		for x in t.bros:
			if c in x:
				t = x[c]
				nobros = False
				break
		if nobros:
			if c not in root:
				t = root
			else:
				t = root[c]
	return t

def railcount(s, t):
	su = 0
	for c in s:
		t = nextmove(t, c, root)
		su += len(t.depo)
	return su
n = int(input())
root = railtree(l)
for i in range(n):
	s = input()
	print(railcount(s, root))


LIMT = 801
two = 1
twos = []
for _ in range(LIMT):
	twos.append(str(two))
	two <<= 1

def inline(s, dct):
	for c in reversed(s):
		if c in dct:
			dct = dct[c]
		else:
			dct[c] = dict()
			dct = dct[c]
	dct[0] = dct.get(0, 0) + 1

def construct_tree(ss):
	dct = dict()
	for s in ss:
		inline(s, dct)
	return dct
twos_dct = construct_tree(twos)

def score(s, dct, i):
	count = 0
	while i >= 0:
		c = s[i]
		if c in dct:
			dct = dct[c]
			count += dct.get(0, 0)
			i -= 1
		else:
			break
	return count

def solve(s):
	return sum((score(s, twos_dct, i) for i in range(len(s))))

def random_string(n=10000):
	import random, string
	return ''.join((string.digits[random.randint(0, 9)] for _ in range(n)))

def test(n=10000):
	return solve(random_string())
T = int(input())
for _ in range(T):
	print(solve(input()))


from collections import deque

class Node:

	def __init__(self, val='', isPower=False, parent=None):
		self.val = val
		self.isPower = isPower
		self.children = {}
		self.parent = parent
		self.failedPointer = None
		self.dictSuffix = None

	def findFailedPointer(self):
		if self.failedPointer is not None:
			return
		if not self.val:
			return
		p = self.parent
		if not p.val:
			self.failedPointer = p
			return
		while p.val:
			if p.failedPointer is None:
				p.findFailedPointer()
			if self.val in p.failedPointer.children:
				self.failedPointer = p.failedPointer.children[self.val]
				return
			p = p.failedPointer
		else:
			self.failedPointer = p
			return

	def findDictSuffix(self):
		node = self.failedPointer
		if node is None:
			return
		while node.val and (not node.isPower):
			node = node.failedPointer
		self.dictSuffix = node if node.val else None
		return
powersOf2 = [str(2 ** i) for i in range(801)]
head = Node()
nodes = []
for s in powersOf2:
	current = head
	for d in s[::-1]:
		if d not in current.children:
			current.children[d] = Node(val=d, parent=current)
		current = current.children[d]
	current.isPower = True
q = deque([head])
while q:
	current = q.popleft()
	current.findFailedPointer()
	current.findDictSuffix()
	q.extend(current.children.values())
N = int(input())
for i in range(N):
	string = input()
	current = head
	points = 0
	for d in string[::-1]:
		while d not in current.children:
			if not current.val:
				break
			current = current.failedPointer
		else:
			current = current.children[d]
			points += int(current.isPower)
			suffix = current.dictSuffix
			while suffix is not None:
				points += 1
				suffix = suffix.dictSuffix
	print(points)


def main():
	tmp = 1
	root = {}
	add_keyword(root, str(tmp))
	for i in range(800):
		tmp *= 2
		add_keyword(root, str(tmp))
	result = []
	T = int(input().strip())
	for i in range(T):
		result.append(find_keyword(root, input()))
	print('\n'.join(result))

def add_keyword(root, keyword):
	length = len(keyword)
	node = root
	for i in range(length):
		char = keyword[i]
		if char in node:
			node = node[char]
		elif i < length:
			if i == length - 1:
				node[char] = {'p': ''}
			else:
				node[char] = {}
			node = node[char]

def find_keyword(root, keyword):
	counter = 0
	length = len(keyword)
	for i in range(length):
		node = root
		for j in range(i, length):
			char = keyword[j]
			if char in node:
				node = node[char]
				if 'p' in node:
					counter = counter + 1
			else:
				break
	return str(counter)
main()


class AhoCorasickTree:

	class Node:

		def __init__(self, label, parent):
			self.label = label
			self.parent = parent
			self.string = False
			self.children = [None] * 10
			self.suffix = None
			self.dictsuffix = None
			self.dictsuffixset = False
			self.stringcount = None

		def GetDictSuffix(self):
			if not self.dictsuffixset:
				self.dictsuffixset = True
				it = self.suffix
				while it is not None and (not it.string):
					it = it.suffix
				self.dictsuffix = it
			return self.dictsuffix

		def GetStringCount(self):
			if self.stringcount is None:
				self.stringcount = 0
				it = self
				while it is not None:
					if it.string:
						self.stringcount += 1
					it = it.GetDictSuffix()
			return self.stringcount

	def __init__(self, strings):
		self.root = AhoCorasickTree.Node(None, None)
		nodes_by_depth = {}
		for s in strings:
			it = self.root
			for (i, d) in enumerate(s):
				if it.children[d] is None:
					newnode = AhoCorasickTree.Node(d, it)
					if i not in nodes_by_depth:
						nodes_by_depth[i] = []
					nodes_by_depth[i].append(newnode)
					it.children[d] = newnode
				it = it.children[d]
			it.string = True
		for depth in sorted(nodes_by_depth.keys()):
			for node in nodes_by_depth[depth]:
				it = node.parent.suffix
				while it is not None and it.children[node.label] is None:
					it = it.suffix
				if it is None:
					node.suffix = self.root
				else:
					node.suffix = it.children[node.label]

	def Count(self, s):
		result = 0
		it = self.root
		for d in s:
			while it is not None and it.children[d] is None:
				it = it.suffix
			if it is None:
				it = self.root
			else:
				it = it.children[d]
				result += it.GetStringCount()
		return result
act = AhoCorasickTree(([int(c) for c in str(2 ** i)] for i in range(801)))
T = int(input())
for l in range(T):
	print(act.Count([int(c) for c in input()]))


class AhoNode:

	def __init__(self):
		self.goto = {}
		self.out = []
		self.fail = None

def aho_create_forest(patterns):
	root = AhoNode()
	for path in patterns:
		node = root
		for symbol in path:
			node = node.goto.setdefault(symbol, AhoNode())
		node.out.append(path)
	return root

def aho_create_statemachine(patterns):
	root = aho_create_forest(patterns)
	queue = []
	for node in root.goto.values():
		queue.append(node)
		node.fail = root
	while len(queue) > 0:
		rnode = queue.pop(0)
		for (key, unode) in rnode.goto.items():
			queue.append(unode)
			fnode = rnode.fail
			while fnode is not None and key not in fnode.goto:
				fnode = fnode.fail
			unode.fail = fnode.goto[key] if fnode else root
			unode.out += unode.fail.out
	return root

def aho_find_all(s, root):
	res = []
	node = root
	for i in range(len(s)):
		while node is not None and s[i] not in node.goto:
			node = node.fail
		if node is None:
			node = root
			continue
		node = node.goto[s[i]]
		for pattern in node.out:
			res.append((i - len(pattern) + 1, pattern))
	return res
patterns = l = {str(2 ** i) for i in range(801)}
root = aho_create_statemachine(patterns)
n = int(input())
for i in range(n):
	s = input()
	print(len(aho_find_all(s, root)))


from collections import deque

def pow_of_two_str(i):
	return str(2 ** i)

def popcnt(x):
	c = 0
	while x != 0:
		x &= x - 1
		c += 1
	return c

def ac_automaton(words):
	goto = [[-1 for _ in range(10)]]
	out = [0]
	states = 1
	for (i, word) in enumerate(words):
		curr_state = 0
		for c in word:
			c = int(c)
			if goto[curr_state][c] == -1:
				goto[curr_state][c] = states
				goto.append([-1 for _ in range(10)])
				out.append(0)
				states += 1
			curr_state = goto[curr_state][c]
		out[curr_state] |= 1 << i
	for c in range(10):
		if goto[0][c] == -1:
			goto[0][c] = 0
	failure = [-1 for _ in range(len(out))]
	queue = deque()
	for c in range(10):
		if goto[0][c] != 0:
			failure[goto[0][c]] = 0
			queue.append(goto[0][c])
	while queue:
		state = queue.popleft()
		for c in range(10):
			if goto[state][c] != -1:
				fail_state = failure[state]
				while goto[fail_state][c] == -1:
					fail_state = failure[fail_state]
				fail_state = goto[fail_state][c]
				out[goto[state][c]] |= out[fail_state]
				failure[goto[state][c]] = fail_state
				queue.append(goto[state][c])
	out = list(map(popcnt, out))
	return (goto, out, failure)

def ac_matches(s, automaton):
	(goto, out, failure) = automaton

	def ac_next_state(state, c):
		next_state = state
		while goto[next_state][c] == -1:
			next_state = failure[next_state]
		return goto[next_state][c]
	count = 0
	curr_state = 0
	for c in s:
		c = int(c)
		curr_state = ac_next_state(curr_state, c)
		count += out[curr_state]
	return count
power_strs = [pow_of_two_str(i) for i in range(800 + 1)]
automaton = ac_automaton(power_strs)
cases = int(input())
for _ in range(cases):
	query = input().strip()
	count = ac_matches(query, automaton)
	print(count)


import sys
n = int(input())
two_powers = set([])
two_powers_itm = set([])
two_powers_len = {}
two_powers_4 = {}
for i1 in range(14):
	t0 = str(2 ** i1)
	two_powers.add(t0)
for i1 in range(0, 10000):
	count = 0
	if i1 < 1000:
		t0 = str(10000 + i1)[-4:]
	else:
		t0 = str(i1)
		for i2 in range(4):
			if t0[:i2 + 1] in two_powers:
				count += 1
	two_powers_4[t0] = count
for i1 in range(14, 801):
	t0 = str(2 ** i1)
	l0 = len(t0)
	two_powers_len[t0[:4]] = l0
	two_powers_itm.add(t0[:4])
	two_powers.add(t0)
for a0 in range(n):
	A = str(input())
	k = len(A)
	count = 0
	for i0 in range(max(0, k - 3)):
		t0 = A[i0:i0 + 4]
		count += two_powers_4[t0]
		if t0 in two_powers_itm:
			l0 = two_powers_len[t0]
			if A[i0:min(i0 + l0, k)] in two_powers:
				count += 1
	if A[-3] == '1' or A[-3] == '2' or A[-3] == '4' or (A[-3] == '8'):
		count += 1
	if A[-2] == '1' or A[-2] == '2' or A[-2] == '4' or (A[-2] == '8'):
		count += 1
	if A[-1] == '1' or A[-1] == '2' or A[-1] == '4' or (A[-1] == '8'):
		count += 1
	if A[-3:-1] == '16' or A[-3:-1] == '32' or A[-3:-1] == '64':
		count += 1
	if A[-2:] == '16' or A[-2:] == '32' or A[-2:] == '64':
		count += 1
	if A[-3:] == '128' or A[-3:] == '256' or A[-3:] == '512':
		count += 1
	print(count)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


import sys
from collections import deque, Counter

class AhoNode:

	def __init__(self):
		self.goto = {}
		self.out = []
		self.fail = None

def aho_create_forest(patterns):
	root = AhoNode()
	for path in patterns:
		node = root
		for symbol in path:
			node = node.goto.setdefault(symbol, AhoNode())
		node.out.append(path)
	return root

def aho_create_statemachine(patterns):
	root = aho_create_forest(patterns)
	queue = []
	for node in root.goto.values():
		queue.append(node)
		node.fail = root
	while len(queue) > 0:
		rnode = queue.pop(0)
		for (key, unode) in rnode.goto.items():
			queue.append(unode)
			fnode = rnode.fail
			while fnode != None and key not in fnode.goto:
				fnode = fnode.fail
			unode.fail = fnode.goto[key] if fnode else root
			unode.out += unode.fail.out
	return root

def aho_find_all(s, root):
	node = root
	for i in range(len(s)):
		while node != None and s[i] not in node.goto:
			node = node.fail
		if node == None:
			node = root
			continue
		node = node.goto[s[i]]
		for pattern in node.out:
			yield (i - len(pattern) + 1, pattern)
aa = aho_create_statemachine((str(2 ** i) for i in range(801)))
n = int(input().strip())
for i in range(n):
	s = input().strip()
	res = sum((1 for (i, x) in aho_find_all(s, aa)))
	print(res)


from collections import deque
ALPHA_N = 10
MAX_ST = 100000
goto = [[-1 for _ in range(ALPHA_N)] for _ in range(MAX_ST)]
fail = [-1 for _ in range(MAX_ST)]
out = [0 for _ in range(MAX_ST)]

def build_pattern():
	ret = []
	pat = 1
	for _ in range(801):
		ret.append(str(pat))
		pat = pat * 2
	return ret

def build_fsm(pattern):
	st = 1
	for i in range(len(pattern)):
		word = pattern[i]
		cur_st = 0
		for j in range(len(word)):
			ch = ord(word[j]) - ord('0')
			if goto[cur_st][ch] == -1:
				goto[cur_st][ch] = st
				st += 1
			cur_st = goto[cur_st][ch]
		out[cur_st] += 1
	for ch in range(ALPHA_N):
		if goto[0][ch] == -1:
			goto[0][ch] = 0
	q = deque()
	for ch in range(ALPHA_N):
		if goto[0][ch] != 0:
			fail[goto[0][ch]] = 0
			q.append(goto[0][ch])
	while len(q):
		st = q.popleft()
		for ch in range(ALPHA_N):
			if goto[st][ch] != -1:
				f = fail[st]
				while goto[f][ch] == -1:
					f = fail[f]
				f = goto[f][ch]
				fail[goto[st][ch]] = f
				out[goto[st][ch]] += out[f]
				q.append(goto[st][ch])
	return st

def next_state(st, ch):
	ans = st
	ch = ord(ch) - ord('0')
	while goto[ans][ch] == -1:
		ans = fail[ans]
	return goto[ans][ch]
pat = build_pattern()
st = build_fsm(pat)
T = int(input().strip())
for _ in range(T):
	s = 0
	word = input().strip()
	st = 0
	for i in range(len(word)):
		st = next_state(st, word[i])
		s += out[st]
	print(s)


n = int(input())
smalls = ['1', '2', '4', '8', '16', '32', '64', '128', '256', '512']
X = [str(2 ** i) for i in range(10, 801)]
d = {x[:4]: x for x in X}
for i in range(n):
	p = input()
	(power, N) = (0, len(p))
	for small in smalls:
		power += p.count(small)
	for i in range(N):
		ss = p[i:i + 4]
		if ss in d:
			pow2 = d[ss]
			if pow2 == p[i:i + len(pow2)]:
				power += 1
	print(power)


class AhoNode:

	def __init__(self):
		self.goto = {}
		self.out = []
		self.fail = None

def aho_create_forest(patterns):
	root = AhoNode()
	for path in patterns:
		node = root
		for symbol in path:
			node = node.goto.setdefault(symbol, AhoNode())
		node.out.append(path)
	return root

def aho_create_statemachine(patterns):
	root = aho_create_forest(patterns)
	queue = []
	for node in root.goto.values():
		queue.append(node)
		node.fail = root
	while len(queue) > 0:
		rnode = queue.pop(0)
		for (key, unode) in rnode.goto.items():
			queue.append(unode)
			fnode = rnode.fail
			while fnode != None and key not in fnode.goto:
				fnode = fnode.fail
			unode.fail = fnode.goto[key] if fnode else root
			unode.out += unode.fail.out
	return root

def aho_find_all(s, root):
	node = root
	found = 0
	for i in range(len(s)):
		while node != None and s[i] not in node.goto:
			node = node.fail
		if node == None:
			node = root
			continue
		node = node.goto[s[i]]
		for pattern in node.out:
			found += 1
	return found
powers = [str(2 ** i) for i in range(0, 801)]
root = aho_create_statemachine(powers)
n = int(input())
for i in range(n):
	print(aho_find_all(input(), root))


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


import os
import sys
tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


import sys
n = int(input())
two_powers = set([])
two_powers_itm = set([])
two_powers_len = {}
two_powers_4 = {}
for i1 in range(14):
	t0 = str(2 ** i1)
	two_powers.add(t0)
for i1 in range(0, 10000):
	count = 0
	if i1 < 1000:
		t0 = str(10000 + i1)[-4:]
	else:
		t0 = str(i1)
		for i2 in range(4):
			if t0[:i2 + 1] in two_powers:
				count += 1
	two_powers_4[t0] = count
for i1 in range(14, 801):
	t0 = str(2 ** i1)
	l0 = len(t0)
	two_powers_len[t0[:4]] = l0
	two_powers_itm.add(t0[:4])
	two_powers.add(t0)
for a0 in range(n):
	A = str(input())
	k = len(A)
	count = 0
	for i0 in range(max(0, k - 3)):
		t0 = A[i0:i0 + 4]
		count += two_powers_4[t0]
		if t0 in two_powers_itm:
			l0 = two_powers_len[t0]
			if A[i0:min(i0 + l0, k)] in two_powers:
				count += 1
	if A[-3] == '1' or A[-3] == '2' or A[-3] == '4' or (A[-3] == '8'):
		count += 1
	if A[-2] == '1' or A[-2] == '2' or A[-2] == '4' or (A[-2] == '8'):
		count += 1
	if A[-1] == '1' or A[-1] == '2' or A[-1] == '4' or (A[-1] == '8'):
		count += 1
	if A[-3:-1] == '16' or A[-3:-1] == '32' or A[-3:-1] == '64':
		count += 1
	if A[-2:] == '16' or A[-2:] == '32' or A[-2:] == '64':
		count += 1
	if A[-3:] == '128' or A[-3:] == '256' or A[-3:] == '512':
		count += 1
	print(count)


from collections import deque
import os

class Node:

	def __init__(self, value, fail=None):
		self.value = value
		self.count = 0
		self.leafs = {}
		if fail == None:
			self.fail = self
		else:
			self.fail = fail

	def create_and_return_leaf(self, value):
		if value not in self.leafs:
			self.leafs[value] = Node(value, self.fail)
		return self.leafs[value]

	def find_fail(self, value):
		fail = self.fail
		while value not in fail.leafs:
			fail = fail.fail
		return fail.leafs[value]

	def next_leaf(self, value):
		if value in self.leafs:
			return self.leafs[value]
		return self.find_fail(value)
mx = 2 ** 800
twos_tree = {}
ct = 1
root = Node(None)
while ct <= mx:
	digits = 0
	tmp = ct
	while tmp >= 10:
		digits += 1
		tmp //= 10
	node = root
	while digits >= 0:
		digit = ct // 10 ** digits % 10
		node = node.create_and_return_leaf(digit)
		digits -= 1
	node.count += 1
	ct *= 2
queue = deque(root.leafs.values())
for k in range(10):
	if k in root.leafs:
		continue
	root.leafs[k] = root
while len(queue) > 0:
	cur = queue.popleft()
	for leaf in cur.leafs.values():
		queue.append(leaf)
		fail = cur.find_fail(leaf.value)
		leaf.fail = fail
		leaf.count += leaf.fail.count
base = ord('0')
n = int(input())
c = 0
while c < n:
	c += 1
	count = 0
	node = root
	for digit in input():
		node = node.next_leaf(ord(digit) - base)
		count += node.count
	print(count)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


import sys
n = int(input())
two_powers = set([])
two_powers_itm = set([])
two_powers_len = {}
two_powers_4 = {}
for i1 in range(14):
	t0 = str(2 ** i1)
	two_powers.add(t0)
for i1 in range(0, 10000):
	count = 0
	if i1 < 1000:
		t0 = str(10000 + i1)[-4:]
	else:
		t0 = str(i1)
		for i2 in range(4):
			if t0[:i2 + 1] in two_powers:
				count += 1
	two_powers_4[t0] = count
for i1 in range(14, 801):
	t0 = str(2 ** i1)
	l0 = len(t0)
	two_powers_len[t0[:4]] = l0
	two_powers_itm.add(t0[:4])
	two_powers.add(t0)
for a0 in range(n):
	A = str(input())
	k = len(A)
	count = 0
	for i0 in range(max(0, k - 3)):
		t0 = A[i0:i0 + 4]
		count += two_powers_4[t0]
		if t0 in two_powers_itm:
			l0 = two_powers_len[t0]
			if A[i0:min(i0 + l0, k)] in two_powers:
				count += 1
	if A[-3] == '1' or A[-3] == '2' or A[-3] == '4' or (A[-3] == '8'):
		count += 1
	if A[-2] == '1' or A[-2] == '2' or A[-2] == '4' or (A[-2] == '8'):
		count += 1
	if A[-1] == '1' or A[-1] == '2' or A[-1] == '4' or (A[-1] == '8'):
		count += 1
	if A[-3:-1] == '16' or A[-3:-1] == '32' or A[-3:-1] == '64':
		count += 1
	if A[-2:] == '16' or A[-2:] == '32' or A[-2:] == '64':
		count += 1
	if A[-3:] == '128' or A[-3:] == '256' or A[-3:] == '512':
		count += 1
	print(count)


def main():
	tmp = 1
	root = {}
	add_keyword(root, str(tmp))
	for i in range(800):
		tmp *= 2
		add_keyword(root, str(tmp))
	result = []
	T = int(input().strip())
	for i in range(T):
		result.append(find_keyword(root, input()))
	print('\n'.join(result))

def add_keyword(root, keyword):
	length = len(keyword)
	node = root
	for i in range(length):
		char = keyword[i]
		if char in node:
			node = node[char]
		elif i < length:
			if i == length - 1:
				node[char] = {'p': ''}
			else:
				node[char] = {}
			node = node[char]

def find_keyword(root, keyword):
	counter = 0
	length = len(keyword)
	for i in range(length):
		node = root
		for j in range(i, length):
			char = keyword[j]
			if char in node:
				node = node[char]
				if 'p' in node:
					counter = counter + 1
			else:
				break
	return str(counter)
main()


n = int(input())
smalls = ['1', '2', '4', '8', '16', '32', '64', '128', '256', '512']
X = [str(2 ** i) for i in range(10, 801)]
d = {x[:4]: x for x in X}
for i in range(n):
	p = input()
	(power, N) = (0, len(p))
	for small in smalls:
		power += p.count(small)
	for i in range(N):
		ss = p[i:i + 4]
		if ss in d:
			pow2 = d[ss]
			if pow2 == p[i:i + len(pow2)]:
				power += 1
	print(power)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


from collections import deque

class Node:

	def __init__(self, val='', isPower=False, parent=None):
		self.val = val
		self.isPower = isPower
		self.children = {}
		self.parent = parent
		self.failedPointer = None
		self.dictSuffix = None

	def findFailedPointer(self):
		if self.failedPointer is not None:
			return
		if not self.val:
			return
		p = self.parent
		if not p.val:
			self.failedPointer = p
			return
		while p.val:
			if p.failedPointer is None:
				p.findFailedPointer()
			if self.val in p.failedPointer.children:
				self.failedPointer = p.failedPointer.children[self.val]
				return
			p = p.failedPointer
		else:
			self.failedPointer = p
			return

	def findDictSuffix(self):
		node = self.failedPointer
		if node is None:
			return
		while node.val and (not node.isPower):
			node = node.failedPointer
		self.dictSuffix = node if node.val else None
		return
powersOf2 = [str(2 ** i) for i in range(801)]
head = Node()
nodes = []
for s in powersOf2:
	current = head
	for d in s[::-1]:
		if d not in current.children:
			current.children[d] = Node(val=d, parent=current)
		current = current.children[d]
	current.isPower = True
q = deque([head])
while q:
	current = q.popleft()
	current.findFailedPointer()
	current.findDictSuffix()
	q.extend(current.children.values())
N = int(input())
for i in range(N):
	string = input()
	current = head
	points = 0
	for d in string[::-1]:
		while d not in current.children:
			if not current.val:
				break
			current = current.failedPointer
		else:
			current = current.children[d]
			points += int(current.isPower)
			suffix = current.dictSuffix
			while suffix is not None:
				points += 1
				suffix = suffix.dictSuffix
	print(points)


def main():
	tmp = 1
	root = {}
	add_keyword(root, str(tmp))
	for i in range(800):
		tmp *= 2
		add_keyword(root, str(tmp))
	result = []
	T = int(input().strip())
	for i in range(T):
		result.append(find_keyword(root, input()))
	print('\n'.join(result))

def add_keyword(root, keyword):
	length = len(keyword)
	node = root
	for i in range(length):
		char = keyword[i]
		if char in node:
			node = node[char]
		elif i < length:
			if i == length - 1:
				node[char] = {'p': ''}
			else:
				node[char] = {}
			node = node[char]

def find_keyword(root, keyword):
	counter = 0
	length = len(keyword)
	for i in range(length):
		node = root
		for j in range(i, length):
			char = keyword[j]
			if char in node:
				node = node[char]
				if 'p' in node:
					counter = counter + 1
			else:
				break
	return str(counter)
main()


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


def main():
	tmp = 1
	root = {}
	add_keyword(root, str(tmp))
	for i in range(800):
		tmp *= 2
		add_keyword(root, str(tmp))
	result = []
	T = int(input().strip())
	for i in range(T):
		result.append(find_keyword(root, input()))
	print('\n'.join(result))

def add_keyword(root, keyword):
	length = len(keyword)
	node = root
	for i in range(length):
		char = keyword[i]
		if char in node:
			node = node[char]
		elif i < length:
			if i == length - 1:
				node[char] = {'p': ''}
			else:
				node[char] = {}
			node = node[char]

def find_keyword(root, keyword):
	counter = 0
	length = len(keyword)
	for i in range(length):
		node = root
		for j in range(i, length):
			char = keyword[j]
			if char in node:
				node = node[char]
				if 'p' in node:
					counter = counter + 1
			else:
				break
	return str(counter)
main()


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import os
import sys
tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


n = int(input())
smalls = ['1', '2', '4', '8', '16', '32', '64', '128', '256', '512']
X = [str(2 ** i) for i in range(10, 801)]
d = {x[:4]: x for x in X}
for i in range(n):
	p = input()
	(power, N) = (0, len(p))
	for small in smalls:
		power += p.count(small)
	for i in range(N):
		ss = p[i:i + 4]
		if ss in d:
			pow2 = d[ss]
			if pow2 == p[i:i + len(pow2)]:
				power += 1
	print(power)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


n = int(input())
vaibhav = []
pushpesh = []
for i in range(0, 13):
	vaibhav.append(str(2 ** i))
for i in range(13, 801):
	pushpesh.append(str(2 ** i))
while n > 0:
	l = []
	l = {i[:4]: i for i in pushpesh}
	n = n - 1
	st = input()
	t = 0
	for i in vaibhav:
		t = t + st.count(i)
	for i in range(len(st)):
		s = st[i:i + 4]
		if s in l:
			raj = l[s]
			if raj == st[i:i + len(raj)]:
				t = t + 1
	print(t)


import os
import sys
import queue

class AhoCorasik(object):

	def __init__(self, n, alphabet, **arg):
		super(AhoCorasik, self).__init__()
		self.arg = arg
		self.n = n
		self.alphabet = alphabet
		self.states = 1
		self.go = [[-1 for x in range(alphabet)] for y in range(n)]
		self.out = [0 for x in range(n)]
		self.fail = [-1 for x in range(n)]

	def add_word(self, s):
		current_state = 0
		for c in s:
			idx = int(c)
			if self.go[current_state][idx] == -1:
				self.go[current_state][idx] = self.states
				self.states += 1
			current_state = self.go[current_state][idx]
		self.out[current_state] += 1

	def build_AC(self):
		Q = queue.Queue(maxsize=0)
		for i in range(self.alphabet):
			if self.go[0][i] == -1:
				self.go[0][i] = 0
			if self.go[0][i] != 0:
				self.fail[self.go[0][i]] = 0
				Q.put(self.go[0][i])
		while not Q.empty():
			current_state = Q.get()
			for i in range(self.alphabet):
				nxt = self.go[current_state][i]
				if nxt == -1:
					continue
				failure = self.fail[current_state]
				while self.go[failure][i] == -1:
					failure = self.fail[failure]
				failure = self.go[failure][i]
				self.fail[self.go[current_state][i]] = failure
				self.out[self.go[current_state][i]] += self.out[failure]
				Q.put(self.go[current_state][i])

	def findNextState(self, current_state, c):
		answer = current_state
		idx = int(c)
		while self.go[answer][idx] == -1:
			answer = self.fail[answer]
		return self.go[answer][idx]

	def searchWords(self, text):
		current_state = 0
		answer = 0
		for c in text:
			current_state = self.findNextState(current_state, c)
			answer += self.out[current_state]
		return answer

def twoTwo(a):
	pass
x = 801
sz = 0
pow2 = [str(1 << i) for i in range(x)]
for x in pow2:
	sz += len(x)
dic = AhoCorasik(sz + 1, 10)
for x in pow2:
	dic.add_word(x)
dic.build_AC()
t = int(input())
for t_itr in range(t):
	a = input()
	result = dic.searchWords(a)
	print(result)


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	a = solve(tree, sys.stdin.readline().strip())
	print(a)


from collections import deque
import os

class Node:

	def __init__(self, value, fail=None):
		self.value = value
		self.count = 0
		self.leafs = {}
		if fail == None:
			self.fail = self
		else:
			self.fail = fail

	def create_and_return_leaf(self, value):
		if value not in self.leafs:
			self.leafs[value] = Node(value, self.fail)
		return self.leafs[value]

	def find_fail(self, value):
		fail = self.fail
		while value not in fail.leafs:
			fail = fail.fail
		return fail.leafs[value]

	def next_leaf(self, value):
		if value in self.leafs:
			return self.leafs[value]
		return self.find_fail(value)
mx = 2 ** 800
twos_tree = {}
ct = 1
root = Node(None)
while ct <= mx:
	digits = 0
	tmp = ct
	while tmp >= 10:
		digits += 1
		tmp //= 10
	node = root
	while digits >= 0:
		digit = ct // 10 ** digits % 10
		node = node.create_and_return_leaf(digit)
		digits -= 1
	node.count += 1
	ct *= 2
queue = deque(root.leafs.values())
for k in range(10):
	if k in root.leafs:
		continue
	root.leafs[k] = root
while len(queue) > 0:
	cur = queue.popleft()
	for leaf in cur.leafs.values():
		queue.append(leaf)
		fail = cur.find_fail(leaf.value)
		leaf.fail = fail
		leaf.count += leaf.fail.count
base = ord('0')
n = int(input())
c = 0
while c < n:
	c += 1
	count = 0
	node = root
	for digit in input():
		node = node.next_leaf(ord(digit) - base)
		count += node.count
	print(count)


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	res = solve(tree, sys.stdin.readline().strip())
	print(res)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


from collections import deque
import os

class Node:

	def __init__(self, value, fail=None):
		self.value = value
		self.count = 0
		self.leafs = {}
		if fail == None:
			self.fail = self
		else:
			self.fail = fail

	def create_and_return_leaf(self, value):
		if value not in self.leafs:
			self.leafs[value] = Node(value, self.fail)
		return self.leafs[value]

	def find_fail(self, value):
		fail = self.fail
		while value not in fail.leafs:
			fail = fail.fail
		return fail.leafs[value]

	def next_leaf(self, value):
		if value in self.leafs:
			return self.leafs[value]
		return self.find_fail(value)
mx = 2 ** 800
twos_tree = {}
ct = 1
root = Node(None)
while ct <= mx:
	digits = 0
	tmp = ct
	while tmp >= 10:
		digits += 1
		tmp //= 10
	node = root
	while digits >= 0:
		digit = ct // 10 ** digits % 10
		node = node.create_and_return_leaf(digit)
		digits -= 1
	node.count += 1
	ct *= 2
queue = deque(root.leafs.values())
for k in range(10):
	if k in root.leafs:
		continue
	root.leafs[k] = root
while len(queue) > 0:
	cur = queue.popleft()
	for leaf in cur.leafs.values():
		queue.append(leaf)
		fail = cur.find_fail(leaf.value)
		leaf.fail = fail
		leaf.count += leaf.fail.count
base = ord('0')
n = int(input())
c = 0
while c < n:
	c += 1
	count = 0
	node = root
	for digit in input():
		node = node.next_leaf(ord(digit) - base)
		count += node.count
	print(count)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


import sys
from collections import deque

class Node(object):

	def __init__(self, ch, transitions=None, results=0, fail=None):
		self.ch = ch
		self.transitions = transitions if transitions else {}
		self.results = 0
		self.fail = fail

	def __repr__(self):
		return 'Node(%r, [...], %r, ...)' % (self.ch, self.results)

def init_tree():
	keywords = []
	p = 1
	while p <= 2 ** 800:
		keywords.append(str(p))
		p *= 2
	root = Node(ch=None, fail=None)
	root.fail = root
	for keyword in keywords:
		current_node = root
		for char in keyword:
			new_node = None
			for (ch, transition) in current_node.transitions.items():
				if ch == char:
					new_node = transition
					break
			if new_node is None:
				new_node = Node(ch=char)
				current_node.transitions[char] = new_node
				if current_node is root:
					new_node.fail = root
			current_node = new_node
		current_node.results = 1
	queue = deque([root])
	while queue:
		current_node = queue.popleft()
		for node in current_node.transitions.values():
			queue.append(node)
			fail_state_node = current_node.fail
			while not fail_state_node.transitions.get(node.ch) and fail_state_node is not root:
				fail_state_node = fail_state_node.fail
			fail = fail_state_node.transitions.get(node.ch, root)
			node.fail = fail if fail is not node else root
			node.results += node.fail.results
	return root

def solve(tree, text):
	result = 0
	current_node = tree
	for c in text:
		while True:
			transition = current_node.transitions.get(c)
			if transition is not None:
				current_node = transition
				break
			if current_node is tree:
				break
			current_node = current_node.fail
		result += current_node.results
	return result
tree = init_tree()
T = int(input())
for t in range(T):
	print(solve(tree, sys.stdin.readline().strip()))


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


from collections import deque
import os

class Node:

	def __init__(self, value, fail=None):
		self.value = value
		self.count = 0
		self.leafs = {}
		if fail == None:
			self.fail = self
		else:
			self.fail = fail

	def create_and_return_leaf(self, value):
		if value not in self.leafs:
			self.leafs[value] = Node(value, self.fail)
		return self.leafs[value]

	def find_fail(self, value):
		fail = self.fail
		while value not in fail.leafs:
			fail = fail.fail
		return fail.leafs[value]

	def next_leaf(self, value):
		if value in self.leafs:
			return self.leafs[value]
		return self.find_fail(value)
mx = 2 ** 800
twos_tree = {}
ct = 1
root = Node(None)
while ct <= mx:
	digits = 0
	tmp = ct
	while tmp >= 10:
		digits += 1
		tmp //= 10
	node = root
	while digits >= 0:
		digit = ct // 10 ** digits % 10
		node = node.create_and_return_leaf(digit)
		digits -= 1
	node.count += 1
	ct *= 2
queue = deque(root.leafs.values())
for k in range(10):
	if k in root.leafs:
		continue
	root.leafs[k] = root
while len(queue) > 0:
	cur = queue.popleft()
	for leaf in cur.leafs.values():
		queue.append(leaf)
		fail = cur.find_fail(leaf.value)
		leaf.fail = fail
		leaf.count += leaf.fail.count
base = ord('0')
n = int(input())
c = 0
while c < n:
	c += 1
	count = 0
	node = root
	for digit in input():
		node = node.next_leaf(ord(digit) - base)
		count += node.count
	print(count)


from collections import deque

class AC:

	def __init__(self, patterns):
		self.next = [[-1] * 10]
		self.output = [0]
		self.strings = patterns
		for i in range(len(patterns)):
			self.trie_add(i)
		self.fail = [-1] * len(self.next)
		self.fail[0] = 0
		self.build_links()

	def trie_add(self, s_id):
		tn = 0
		for c in self.strings[s_id]:
			i = ord(c) - ord('0')
			if self.next[tn][i] < 0:
				self.next[tn][i] = len(self.next)
				self.next.append([-1] * 10)
				self.output.append(0)
			tn = self.next[tn][i]
		self.output[tn] = 1

	def build_links(self):
		q = deque()
		for c in range(10):
			tn = self.next[0][c]
			if tn < 0:
				self.next[0][c] = 0
			else:
				self.fail[tn] = 0
				q.append(tn)
		while len(q) > 0:
			tn = q.popleft()
			for c in range(10):
				nx = self.next[tn][c]
				if nx < 0:
					continue
				q.append(nx)
				x = self.fail[tn]
				while self.next[x][c] < 0:
					x = self.fail[x]
				self.fail[nx] = self.next[x][c]
				self.output[nx] += self.output[self.fail[nx]]

	def search(self, s):
		res = 0
		tn = 0
		ss = [ord(c) - ord('0') for c in s]
		for c in ss:
			while self.next[tn][c] < 0:
				tn = self.fail[tn]
			tn = self.next[tn][c]
			res += self.output[tn]
		return res
pwrs = []
p = 1
for i in range(801):
	pwrs.append(str(p))
	p <<= 1
ac = AC(pwrs)
t = int(input())
for _ in range(t):
	a = input().strip()
	print(ac.search(a))


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


n = int(input())
smalls = ['1', '2', '4', '8', '16', '32', '64', '128', '256', '512']
X = [str(2 ** i) for i in range(10, 801)]
d = {x[:4]: x for x in X}
for i in range(n):
	p = input()
	(power, N) = (0, len(p))
	for small in smalls:
		power += p.count(small)
	for i in range(N):
		ss = p[i:i + 4]
		if ss in d:
			pow2 = d[ss]
			if pow2 == p[i:i + len(pow2)]:
				power += 1
	print(power)


from collections import deque
import os

class Node:

	def __init__(self, value, fail=None):
		self.value = value
		self.count = 0
		self.leafs = {}
		if fail == None:
			self.fail = self
		else:
			self.fail = fail

	def create_and_return_leaf(self, value):
		if value not in self.leafs:
			self.leafs[value] = Node(value, self.fail)
		return self.leafs[value]

	def find_fail(self, value):
		fail = self.fail
		while value not in fail.leafs:
			fail = fail.fail
		return fail.leafs[value]

	def next_leaf(self, value):
		if value in self.leafs:
			return self.leafs[value]
		return self.find_fail(value)
mx = 2 ** 800
twos_tree = {}
ct = 1
root = Node(None)
while ct <= mx:
	digits = 0
	tmp = ct
	while tmp >= 10:
		digits += 1
		tmp //= 10
	node = root
	while digits >= 0:
		digit = ct // 10 ** digits % 10
		node = node.create_and_return_leaf(digit)
		digits -= 1
	node.count += 1
	ct *= 2
queue = deque(root.leafs.values())
for k in range(10):
	if k in root.leafs:
		continue
	root.leafs[k] = root
while len(queue) > 0:
	cur = queue.popleft()
	for leaf in cur.leafs.values():
		queue.append(leaf)
		fail = cur.find_fail(leaf.value)
		leaf.fail = fail
		leaf.count += leaf.fail.count
base = ord('0')
n = int(input())
c = 0
while c < n:
	c += 1
	count = 0
	node = root
	for digit in input():
		node = node.next_leaf(ord(digit) - base)
		count += node.count
	print(count)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


n = int(input())
smalls = ['1', '2', '4', '8', '16', '32', '64', '128', '256', '512']
X = [str(2 ** i) for i in range(10, 801)]
d = {x[:4]: x for x in X}
for i in range(n):
	p = input()
	(power, N) = (0, len(p))
	for small in smalls:
		power += p.count(small)
	for i in range(N):
		ss = p[i:i + 4]
		if ss in d:
			pow2 = d[ss]
			if pow2 == p[i:i + len(pow2)]:
				power += 1
	print(power)


import string

class Trie:

	def __init__(self, s_id=None):
		self.s_id = s_id
		self.edges = {}
		self.err_f = None
		self.out = set()
		if self.s_id is not None:
			out.add(self.s_id)
		self.out_l = len(self.out)

	def add_s(self, s, s_id):
		if len(s) == 0:
			self.s_id = s_id
			self.out.add(s_id)
			self.out_l = len(self.out)
			return
		c1 = s[0]
		cn = s[1:]
		if c1 not in self.edges:
			self.edges[c1] = Trie()
		self.edges[c1].add_s(cn, s_id)

	def match(self, s):
		if len(s) == 0:
			return self.s_id is not None
		c1 = s[0]
		cn = s[1:]
		if c1 in self.edges:
			return self.edges[c1].match(cn)
		else:
			return False

	def ac_match(self, s):
		count = 0
		q = self
		for c in s:
			while c not in q.edges and q is not self:
				q = q.err_f
			if q is self and c not in q.edges:
				continue
			q = q.edges[c]
			count += q.out_l
		return count
n = int(input())
graph = Trie()
for i in range(801):
	graph.add_s(str(2 ** i), i)
q = []
graph.err_f = graph
for a in graph.edges:
	graph.edges[a].err_f = graph
	q.append(graph.edges[a])
while len(q) > 0:
	r = q.pop(0)
	for a in r.edges:
		q.append(r.edges[a])
		v = r.err_f
		while v is not graph and a not in v.edges:
			v = v.err_f
		u = r.edges[a]
		if a not in v.edges:
			u.err_f = graph
		else:
			u.err_f = v.edges[a]
		u.out = u.out | u.err_f.out
		u.out_l = len(u.out)
for x in range(n):
	s = input().strip()
	print(graph.ac_match(s))


LIMIT = 801
two = 1
twos = []
for _ in range(LIMIT):
	twos.append(str(two))
	two <<= 1

def inline(s, dct):
	for c in reversed(s):
		if c in dct:
			dct = dct[c]
		else:
			dct[c] = dict()
			dct = dct[c]
	dct[0] = dct.get(0, 0) + 1

def construct_tree(ss):
	dct = dict()
	for s in ss:
		inline(s, dct)
	return dct
twos_dct = construct_tree(twos)

def score(s, dct, i):
	count = 0
	while i >= 0:
		c = s[i]
		if c in dct:
			dct = dct[c]
			count += dct.get(0, 0)
			i -= 1
		else:
			break
	return count

def solve(s):
	return sum((score(s, twos_dct, i) for i in range(len(s))))

def random_string(n=10000):
	import random, string
	return ''.join((string.digits[random.randint(0, 9)] for _ in range(n)))

def test(n=10000):
	return solve(random_string())
T = int(input())
for _ in range(T):
	print(solve(input()))


from collections import deque, namedtuple
import functools
import sys

class Node(object):

	def __init__(self, parent, data):
		self.term = False
		self.has_term = 0
		self.childs = [None] * 10
		self.parent = parent
		self.suf = None
		self.data = data
		self.go = [None] * 10

def index(c):
	return int(c)

def add(root, S):
	cur = root
	for c in S:
		if not cur.childs[index(c)]:
			cur.childs[index(c)] = Node(cur, c)
		cur = cur.childs[index(c)]
	cur.term = True

@functools.lru_cache(maxsize=None)
def suf(cur):
	if not cur.suf:
		cur.suf = go(suf(cur.parent), cur.data)
	return cur.suf

@functools.lru_cache(maxsize=None)
def go(cur, c):
	if not cur.go[index(c)]:
		if not cur.childs[index(c)]:
			cur.go[index(c)] = go(suf(cur), c)
		else:
			cur.go[index(c)] = cur.childs[index(c)]
	return cur.go[index(c)]
fake_root = Node(None, '')
root = Node(fake_root, '')
fake_root.childs = [root] * 10
root.suf = fake_root
for i in range(0, 801):
	add(root, str(pow(2, i)))
q = deque([root])
while len(q) > 0:
	nxt = q.popleft()
	nxt.has_term = int(nxt.term) + suf(nxt).has_term
	for ch in nxt.childs:
		if ch:
			q.append(ch)
t = int(input())
for _ in range(t):
	s = input()
	cur = root
	ans = 0
	for c in s:
		cur = go(cur, c)
		ans += cur.has_term
	print(ans)


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


n = int(input())
smalls = ['1', '2', '4', '8', '16', '32', '64', '128', '256', '512']
X = [str(2 ** i) for i in range(10, 801)]
d = {x[:4]: x for x in X}
for i in range(n):
	p = input()
	(power, N) = (0, len(p))
	for small in smalls:
		power += p.count(small)
	for i in range(N):
		ss = p[i:i + 4]
		if ss in d:
			pow2 = d[ss]
			if pow2 == p[i:i + len(pow2)]:
				power += 1
	print(power)


import math
import os
import random
import re
import sys
tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])


tree = [False, {}]

def add(word):
	current = tree
	for c in word:
		try:
			current = current[1][c]
		except KeyError:
			current[1][c] = [False, {}]
			current = current[1][c]
	current[0] = True

def count(word):
	count = 0
	for start in range(len(word)):
		(current, index) = (tree, start)
		while True:
			if current[0]:
				count += 1
			try:
				current = current[1][word[index]]
				index += 1
			except (KeyError, IndexError):
				break
	return count
v = 1
for x in range(801):
	add(str(v)[::-1])
	v <<= 1
Done = {}
T = int(input())
for t in range(T):
	A = input()
	if not A in Done:
		Done[A] = count(A[::-1])
	print(Done[A])