Chef has just learned a new data structure - Fenwick tree. This data structure holds information about array of N elements and can process two types of operations:

- Add some value to ith element of the array
- Calculate sum of all elements on any prefix of the array

Both operations take O(log N) time. This data structure is also well known for its low memory usage. To be more precise, it needs exactly the same amount of memory as that of array.

Given some array A, first we build data structure in some other array T. Ti stores the sum of the elements Astart, Astart + 1, ..., Ai. Index start is calculated with formula start = Fdown(i) = (i & (i + 1)). Here "&" denotes bitwise AND operation.
So, in order to find a sum of elements A0, A1, ..., AL you start with index L and calculate sum of TL + TFdown(L)-1 + TFdown(Fdown(L)-1)-1 + ... + TFdown(Fdown(...(Fdown(L)-1)-1)-1. Usually it is performed with cycle that goes from L down to 0 with function Fdown and sums some elements from T. Chef wants to verify that the time complexity to calculate sum of A0, A1, A2, ..., AL is O(log L). In order to do so, he wonders how many times he has to access array T to calculate this sum. Help him to find this out.
Since Chef works with really big indices. The value of L can be very large and is provided to you in binary representation as concatenation of strings L1, L2 repeated N times and string L3.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains three non-empty strings L1, L2, L3 and an integer N. Strings will contain only characters 0 and 1. To obtain binary representation of index L concatenate L1 with L2 repeated N times and with L3. You are guaranteed that the index will be positive.

-----Output-----
For each test case, output a single line containing number of times Fenwick tree data structure will access array T in order to compute sum of A0, A1, A2, ..., AL.

-----Constraints-----
- 1 ≤ T ≤ 300
- 1 ≤ Length(Li) ≤ 1000
- 1 ≤ N ≤ 106

-----Subtasks-----
- Subtask #1 (20 points): |L1| + |L2| * N + |L3| ≤ 60
- Subtask #2 (30 points): 1 ≤ T ≤ 30, 1 ≤ N ≤ 100
- Subtask #3 (50 points): No additional constraints

-----Example-----
Input:
4
001 100 011 4
1000 1101 100 3
1010 001 101 4
010 101 000 4

Output:
6
12
8
10

Difficulty: MEDIUM_HARD
Tags: Bit manipulation
Skill types: Bit manipulation

Starter code:

Solutions:
t = input()
t = int(t)
while t:
	(l1, l2, l3, n) = input().split()
	n = int(n)
	counter = 0
	t = t - 1
	if l3.count('1') == len(l3):
		if l2.count('1') == len(l2):
			if l1.count('1') == len(l1):
				counter = 1
				print(counter)
				continue
			else:
				temp = int(l1, 2)
				temp += 1
				counter += bin(temp).count('1')
				print(counter)
				continue
		else:
			temp = int(l2, 2)
			temp += 1
			counter += bin(temp).count('1')
			counter += l1.count('1')
			counter += (n - 1) * l2.count('1')
			print(counter)
			continue
	else:
		temp = int(l3, 2)
		temp += 1
		counter += bin(temp).count('1')
		counter += l1.count('1')
		counter += n * l2.count('1')
		print(counter)
		continue


t = int(input())
for i in range(t):
	(l1, l2, l3, n) = input().strip().split(' ')
	n = int(n)
	cnt = 0
	if l3.count('0') == 0:
		if l2.count('0') == 0:
			ll1 = bin(int(l1, 2) + 1)
			ll1 = ll1[2:len(ll1)]
			cnt = ll1.count('1')
		else:
			ll2 = bin(int(l2, 2) + 1)
			ll2 = ll2[2:len(ll2)]
			cnt += l2.count('1') * (n - 1) + ll2.count('1')
			cnt += l1.count('1')
	else:
		ll3 = bin(int(l3, 2) + 1)
		ll3 = ll3[2:len(ll3)]
		cnt += ll3.count('1') + l2.count('1') * n + l1.count('1')
	print(cnt)


for _ in range(int(input())):
	(l1, l2, l3, n) = [x for x in input().split()]
	allOne = 0
	count = 0
	last = len(l3) - 1
	countl3 = l3.count('1')
	countl2 = l2.count('1')
	countl1 = l1.count('1')
	totalOne = countl1 + countl2 * int(n) + countl3
	if len(l3) == countl3:
		count += countl3
		allOne = 1
	else:
		while l3[last] == '1' and last >= 0:
			count += 1
			last -= 1
	if allOne == 1:
		if len(l2) == countl2:
			count += countl2 * int(n)
		else:
			allOne = 0
			last = len(l2) - 1
			while l2[last] == '1' and last >= 0:
				count += 1
				last -= 1
	if allOne == 1:
		if len(l1) == countl1:
			count += countl1
		else:
			allOne = 0
			last = len(l1) - 1
			while l1[last] == '1' and last >= 0:
				count += 1
				last -= 1
	print(totalOne + 1 - count)


for t in range(eval(input())):
	lis = input().split()
	c3 = 0
	flag = False
	for i in reversed(lis[2]):
		if flag and i == '1':
			c3 += 1
		elif i == '0':
			flag = True
	c2 = 0
	c21 = 0
	for i in reversed(lis[1]):
		if i == '1':
			c21 += 1
			if flag:
				c2 += 1
		elif i == '0':
			flag = True
	if flag:
		c2 += (eval(lis[3]) - 1) * c21
	c1 = 0
	for i in reversed(lis[0]):
		if flag and i == '1':
			c1 += 1
		elif i == '0':
			flag = True
	print(c1 + c2 + c3 + 1)


import sys
sys.setrecursionlimit(10 ** 9)

def pad(s):
	if s == '':
		return s
	if s[0] == '0':
		return pad(s[1:])
	return s

def pad1(s):
	if s == '':
		return s
	if s[0] == '1':
		return pad1(s[1:])
	return s
t = int(input())
while t > 0:
	t -= 1
	(s1, s2, s3, n) = map(str, input().split())
	n = int(n)
	if n <= 10:
		s = s1 + n * s2 + s3
		s = pad(s)[::-1]
		s = pad1(s)
		print(s.count('1') + 1)
	else:
		n -= 2
		if pad(s1 + s2) == '':
			s3 = pad1(pad(s3)[::-1])
			print(s3.count('1') + 1)
		elif pad1((s2 + s3)[::-1]) == '':
			s1 = pad1(pad(s1)[::-1])
			print(s1.count('1') + 1)
		else:
			s1 += s2
			s1 = pad(s1)
			s3 = s2 + s3
			s3 = s3[::-1]
			s3 = pad1(s3)
			print(s1.count('1') + n * s2.count('1') + s3.count('1') + 1)


import sys
t = int(input())
for i in range(t):
	s = input().strip().split()
	n = int(s[3])
	l1 = ''
	l2 = ''
	l3 = ''
	if s[2][-1] == '0':
		print(1 + s[0].count('1') + n * s[1].count('1') + s[2].count('1'))
	else:
		l3 = bin(int(s[2], 2) + 1)[2:]
		if len(l3) <= len(s[2]):
			print(s[0].count('1') + n * s[1].count('1') + l3.count('1'))
		elif s[1][-1] == '0':
			print(1 + s[0].count('1') + n * s[1].count('1') + (l3.count('1') - 1))
		else:
			l2 = bin(int(s[1], 2) + 1)[2:]
			if len(l2) <= len(s[1]):
				print(s[0].count('1') + (n - 1) * s[1].count('1') + l2.count('1') + (l3.count('1') - 1))
			elif s[0][-1] == '0':
				print(1 + s[0].count('1') + n * l2[1:].count('1') + l3[1:].count('1'))
			else:
				l1 = bin(int(s[0], 2) + 1)[2:]
				print(l1.count('1') + n * l2[1:].count('1') + l3[1:].count('1'))


t = int(input())
for i in range(t):
	(l1, l2, l3, n) = map(str, input().split())
	len1 = l1.count('1')
	len2 = l2.count('1')
	len3 = l3.count('1')
	if len3 == len(l3):
		if len2 == len(l2):
			if len1 == len(l1):
				print(1)
			else:
				ind = -1
				while l1[ind] != '0':
					ind = ind - 1
				print(max(0, len1 + ind + 1) + 1)
		else:
			ind = -1
			while l2[ind] != '0':
				ind = ind - 1
			print(len2 * (int(n) - 1) + len1 + max(0, len2 + ind + 1) + 1)
	elif l3[-1] == '1':
		ind = -1
		while l3[ind] != '0':
			ind = ind - 1
		print(len1 + len2 * int(n) + max(0, len3 + ind + 1) + 1)
	else:
		print(len1 + len2 * int(n) + len3 + 1)


for t in range(int(input())):
	(s, s1, s2, n) = [i for i in input().split()]
	sf = s
	co = 0
	l = len(s)
	l1 = len(s1)
	l2 = len(s2)
	ns = s.count('1')
	ns1 = s1.count('1')
	ns2 = s2.count('1')
	co = ns + ns1 * int(n) + ns2
	if s2[l2 - 1] == '0':
		co += 1
	elif co == l + l1 * int(n) + l2:
		co = 1
	else:
		f = 1
		if ns2 > 0:
			if ns2 == l2:
				co -= ns2
			else:
				for i in s2[::-1]:
					if i == '0':
						f = 0
						co += 1
						break
					co -= 1
		else:
			co += 1
			f = 0
		if f == 1:
			if ns1 > 0:
				if ns1 == l1:
					co -= ns1 * int(n)
				else:
					for i in s1[::-1]:
						if i == '0':
							f = 0
							co += 1
							break
						co -= 1
			else:
				co += 1
				f = 0
		if f == 1:
			if ns > 0:
				if ns == l:
					co -= ns
				else:
					for i in s[::-1]:
						if i == '0':
							f = 0
							co += 1
							break
						co -= 1
			else:
				co += 1
				f = 0
	print(co)


tes = int(input())
for _ in range(tes):
	(a, b, c, n) = [x for x in input().split()]
	n = int(n)
	ans = switch = 0
	for i in range(len(c) - 1, -1, -1):
		if switch == 0:
			if c[i] == '0':
				switch = 1
				ans += 1
		if switch == 1:
			if c[i] == '1':
				ans += 1
	for i in range(len(b) - 1, -1, -1):
		if switch == 0:
			if b[i] == '0':
				switch = 1
				ans += 1
		if switch == 1:
			if b[i] == '1':
				ans += 1
	for i in range(len(b) - 1, -1, -1):
		if switch == 0:
			if b[i] == '0':
				switch = 1
				ans += n - 1
		if switch == 1:
			if b[i] == '1':
				ans += n - 1
	for i in range(len(a) - 1, -1, -1):
		if switch == 0:
			if a[i] == '0':
				switch = 1
				ans += 1
		if switch == 1:
			if a[i] == '1':
				ans += 1
	if switch == 0:
		ans = 1
	print(ans)


t = int(input())
for i in range(t):
	(l1, l2, l3, n) = map(lambda x: x.strip(), list(input().split()))
	n = int(n)
	x = l3.rfind('0')
	if x == -1:
		y = l2.rfind('0')
		if y == -1:
			z = l1.rfind('0')
			if z == -1:
				print(1)
			else:
				print(1 + l1.count('1', 0, z))
		else:
			count = l2.count('1') * n + l1.count('1') - l2.count('1', y)
			print(1 + count)
	elif x == len(l3) - 1:
		count = l3.count('1') + l2.count('1') * n + l1.count('1')
		print(1 + count)
	else:
		count = l3.count('1') - l3.count('1', x) + l2.count('1') * n + l1.count('1')
		print(1 + count)


t = int(input())
while t:
	t -= 1
	inp = input().split()
	n = int(inp[3])
	inp_1 = inp[0]
	inp_2 = inp[1]
	inp_3 = inp[2]
	len1 = len(inp_1)
	len2 = len(inp_2)
	len3 = len(inp_3)
	count = 1
	c = len3 - 1
	found_zero = 0
	while c >= 0:
		if inp_3[c] == '0':
			found_zero = 1
			c -= 1
			continue
		elif found_zero:
			count += 1
			c -= 1
		else:
			c -= 1
	c = len2 - 1
	cnt = 0
	while c >= 0:
		if inp_2[c] == '0':
			found_zero = 1
			c -= 1
			continue
		elif found_zero:
			count += n
			c -= 1
		else:
			cnt += 1
			c -= 1
	if found_zero:
		count += (n - 1) * cnt
	c = len1 - 1
	while c >= 0:
		if inp_1[c] == '0':
			found_zero = 1
			c -= 1
			continue
		elif found_zero:
			count += 1
			c -= 1
		else:
			c -= 1
	print(count)


t = int(input())
for i in range(0, t):
	count = 0
	(l1, l2, l3, n) = map(str, input().split())
	N = int(n)
	L = int(l3, 2)
	if len(l3) == l3.count('1'):
		if len(l2) == l2.count('1'):
			l = int(l1, 2) + 1
			l1 = bin(l)
			L1 = l1.count('1')
		else:
			l4 = l2
			l = int(l4, 2) + 1
			l4 = bin(l)
			n1 = l4.count('1')
			n2 = (N - 1) * l2.count('1')
			n3 = l1.count('1')
			L1 = n1 + n2 + n3
	else:
		L = L + 1
		l3 = bin(L)
		L1 = l1.count('1') + N * l2.count('1') + l3.count('1')
	print(L1)


t = int(input())
count = []
for i in range(t):
	s = input()
	(a, b, c, n) = s.split()
	n = int(n)
	d = int(a + b * n + c, 2)
	count.append(0)
	while d > 0:
		d = (d & d + 1) - 1
		count[i] += 1
for i in range(t):
	print(count[i])


for _ in range(int(input())):
	(l1, l2, l3, n) = [i for i in input().split()]
	n = int(n)
	if l3.find('0') == -1:
		if l2.find('0') == -1:
			if l1.find('0') == -1:
				print(1)
			else:
				s = l1[::-1]
				for i in range(len(s)):
					if s[i] == '0':
						s = s[i:]
						break
				print(s.count('1') + 1)
		else:
			s = l2[::-1]
			cnt = 0
			for i in range(len(s)):
				if s[i] == '0':
					s = s[i:]
					break
				else:
					cnt += 1
			print(l2.count('1') * n + l1.count('1') - cnt + 1)
	else:
		s = l3[::-1]
		for i in range(len(s)):
			if s[i] == '0':
				s = s[i:]
				break
		print(s.count('1') + l1.count('1') + l2.count('1') * n + 1)


T = int(input())
for _t in range(T):
	(a, b, c, n) = input().strip().split(' ')
	n = int(n)
	ans = 0
	if '0' not in a + b + c:
		ans = 1
	elif '1' not in a + b + c:
		ans = 0
	else:
		if '0' in c:
			ans = 0
		elif '0' in b:
			c = b
			n -= 1
		elif '0' in a:
			c = a
			n = 0
			a = ''
		c = list(c)
		for i in range(len(c) - 1, -1, -1):
			if c[i] == '1':
				c[i] = '0'
			else:
				c[i] = '1'
				break
		ans = a.count('1') + n * b.count('1') + c.count('1')
	print(ans)


t = int(input())
for i in range(t):
	(l1, l2, l3, n) = input().split()
	n = int(n)
	c = l1.count('1') + l2.count('1') * n + l3.count('1')
	(len1, len2, len3) = (len(l1), len(l2), len(l3))
	if l3[-1] == '0':
		print(c + 1)
	elif l3[-1] == '1':
		r = l3.rindex('0') if '0' in l3 else -1
		if r != -1:
			print(c - (len3 - (r + 1)) + 1)
			continue
		r = l2.rindex('0') if '0' in l2 else -1
		if r != -1:
			print(c - (len3 + len2 - (r + 1)) + 1)
			continue
		r = l1.rindex('0') if '0' in l1 else -1
		if r != -1:
			print(c - (len1 + len3 + len2 * n - (r + 1)) + 1)
			continue
		print(1)


for _ in range(int(input())):
	l = input().split()
	cnt = 0
	for c in l[1]:
		cnt += c == '1'
	cnt *= int(l[3])
	for c in l[0]:
		cnt += c == '1'
	for c in l[2]:
		cnt += c == '1'
	i = len(l[2]) - 1
	while i >= 0 and l[2][i] == '1':
		cnt -= 1
		i -= 1
	if l[2] == '1' * len(l[2]):
		if l[1] != '1' * len(l[1]):
			i = len(l[1]) - 1
			while i >= 0 and l[1][i] == '1':
				cnt -= 1
				i -= 1
		else:
			if l[0] != len(l[0]) * '1':
				i = len(l[0]) - 1
				while i >= 0 and l[0][i] == '1':
					cnt -= 1
					i -= 1
			else:
				cnt -= len(l[0])
			cnt -= int(l[3]) * len(l[1])
	cnt += 1
	print(cnt)


for z in range(int(input())):
	li = [i for i in input().split()]
	(ans, temp) = (0, 0)
	if li[2][-1] == '0':
		ans = 1
		for i in li[0]:
			if i == '1':
				ans += 1
		for i in li[1]:
			if i == '1':
				temp += 1
		temp *= int(li[3])
		ans += temp
		for i in li[2]:
			if i == '1':
				ans += 1
	else:
		(zc, dex) = (-1, 0)
		for i in li[2][::-1]:
			if zc == 0:
				if i == '1':
					ans += 1
			if i == '0':
				zc = 0
		if zc == 0:
			for i in li[1]:
				if i == '1':
					temp += 1
			temp *= int(li[3])
			ans += temp
			for i in li[0]:
				if i == '1':
					ans += 1
		else:
			for i in li[1][::-1]:
				if zc == 0:
					if i == '1':
						ans += 1
				if i == '0':
					zc = 0
			if zc == 0:
				for i in li[1]:
					if i == '1':
						temp += 1
				temp *= int(li[3]) - 1
				ans += temp
				for i in li[0]:
					if i == '1':
						ans += 1
			else:
				for i in li[0][::-1]:
					if zc == 0:
						if i == '1':
							ans += 1
					if i == '0':
						zc = 0
		ans += 1
	print(ans)


t = int(input())
i = 0
while i < t:
	(l1, l2, l3, N) = input().strip().split(' ')
	N = int(N)
	if (l1.count('0') == 0 and l2.count('0') == 0) and l3.count('0') == 0:
		print('1')
	elif l3.count('0') == 0 and l2.count('0') == 0:
		s1 = bin(int(l1, 2) + 1)
		s1 = s1[2:len(s1)]
		print(s1.count('1'))
	elif l3.count('0') == 0:
		s1 = bin(int(l2, 2) + 1)
		s1 = s1[2:len(s1)]
		print(l1.count('1') + l2.count('1') * (N - 1) + s1.count('1'))
	else:
		s1 = bin(int(l3, 2) + 1)
		l3 = s1[2:len(s1)]
		print(l1.count('1') + l2.count('1') * N + l3.count('1'))
	i += 1


for Fewti in range(int(input())):
	(a, b, c, n) = map(str, input().split())
	n = int(n)
	s = a + b + c
	ca = a.count('1')
	cb = b.count('1')
	cc = c.count('1')
	c = ca + n * cb + cc
	i = len(s) - 1
	l = i + 1
	while i >= 0:
		if s[i] == '0':
			break
		i -= 1
	if i == l - 1:
		print(c + 1)
	elif i == -1:
		print(1)
	elif i <= len(a) - 1:
		print(c - (len(a) - i - 1) + 1 - (n * cb + cc))
	else:
		print(c - (l - i - 1) + 1)


def check(s):
	size = len(s)
	(end, total, found) = (0, 0, True)
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			found = False
		if found:
			end += 1
		if s[i] == '1':
			total += 1
	return (total, end, size)
for i in range(int(input())):
	l = list(map(str, input().split()))
	s1 = check(l[0])
	s2 = check(l[1])
	s3 = check(l[2])
	if s3[2] != s3[1]:
		ans = s1[0] + int(l[3]) * s2[0] + s3[0] - s3[1] + 1
	elif s2[2] != s2[1]:
		ans = s1[0] + (int(l[3]) - 1) * s2[0] + s2[0] - s2[1] + 1
	elif s1[2] != s1[1]:
		ans = s1[0] - s1[1] + 1
	else:
		ans = 1
	print(ans)


t = int(input())
while t > 0:
	(l1, l2, l3, n) = map(str, input().split())
	n = int(n)
	a = bin(int(l3, 2) + 1)
	if len(a) > len(l3) + 2:
		a = bin(int(l2, 2) + 1)
		if len(a) > len(l2) + 2:
			a = bin(int(l1, 2) + 1)
			if len(a) > len(l1) + 2:
				print(1)
			else:
				print(a.count('1'))
		else:
			print(l2.count('1') * (n - 1) + a.count('1') + l1.count('1'))
	else:
		print(a.count('1') + l2.count('1') * n + l1.count('1'))
	t -= 1


def plusone(s):
	for i in range(len(s) - 1, -1, -1):
		if s[i] == '0':
			s[i] = '1'
			return i
		else:
			s[i] = '0'
	return -1

def countones(s):
	cnt = 0
	for c in s:
		if c == '1':
			cnt += 1
	return cnt
T = int(input())
for t in range(T):
	S = input().split()
	(L1, L2, L3, N) = (list(S[0]), list(S[1]), list(S[2]), int(S[3]))
	L2x = list(L2)
	N -= 1
	cnt = 0
	y = 100
	x = plusone(L3)
	if x == -1:
		y = plusone(L2x)
		if y == -1:
			z = plusone(L1)
			if z == -1:
				L1 = ['1']
	cnt = countones(L3)
	if y >= 0:
		cnt += countones(L2x) + N * countones(L2)
	cnt += countones(L1)
	print(cnt)


def fdown(i):
	return i & i + 1

def actual_answer(value):
	count = 0
	while value > 0:
		value = fdown(value) - 1
		count += 1
	return count
t = int(input())
while t > 0:
	t -= 1
	(l1, l2, l3, n) = input().split()
	n = int(n)
	case1 = int(l1 + l2 + l3, base=2)
	case2 = int(l1 + l2 * 2 + l3, base=2)
	count_case1 = actual_answer(case1)
	count_case2 = actual_answer(case2)
	diff = count_case2 - count_case1
	answer = count_case1 + (n - 1) * diff
	print(answer)


def add_one(n, add_carry=False):
	n = list(n)
	l = len(n)
	carry = 1
	for i in range(l - 1, -1, -1):
		if carry == 1:
			if n[i] == '1':
				n[i] = '0'
			else:
				n[i] = '1'
				carry = 0
	if add_carry and carry == 1:
		n.insert(0, '1')
	return (''.join(n), carry)

def complex_add_one(l1, l2, l3, n):
	(l3, l3_c) = add_one(l3)
	if l3_c == 0:
		return (l1, l2, l3, n)
	l2_old = l2
	(l2, l2_c) = add_one(l2)
	if l2_c == 0:
		return (l1, l2_old, l2 + l3, n - 1)
	(l1, l1_c) = add_one(l1)
	if l1_c == 1:
		l1 = '1' + l1
	return (l1, l2, l3, n)

def count_ones(n):
	return sum([1 for c in n if c == '1'])

def complex_count_ones(l1, l2, l3, n):
	return count_ones(l1) + n * count_ones(l2) + count_ones(l3)

def expand(l1, l2, l3, n):
	return l1 + n * l2 + l3

def compute():
	z = input().split()
	z[3] = int(z[3])
	z = complex_add_one(*z)
	print(complex_count_ones(*z))
t = int(input())
for _ in range(t):
	compute()


def inc(b):
	for (i, c) in reversed(list(enumerate(b))):
		if c == '0':
			b[i] = '1'
			break
		b[i] = '0'
	else:
		return 1
	return 0
for _ in range(int(input())):
	(a, b, c, n) = input().split()
	(a, b, c) = (list(x) for x in (a, b, c))
	n = int(n)
	r = 0
	if inc(c):
		t = b.count('1')
		if inc(b):
			r += inc(a)
			r += a.count('1')
		else:
			r += a.count('1')
			r += b.count('1')
			r += t * (n - 1)
	else:
		r += a.count('1')
		r += b.count('1') * n
		r += c.count('1')
	print(r)


for t in range(int(input())):
	l = list(input().strip().split())
	l[3] = int(l[3])
	str2 = l[2]
	str2 = str2[::-1]
	flag = [False] * 3
	count = 1
	i = 0
	while i < len(str2) and str2[i] == '1':
		i += 1
	if i == len(str2):
		flag[2] = True
	if not flag[2]:
		count = count + str2[i:].count('1') + l[1].count('1') * l[3] + l[0].count('1')
	elif flag[2]:
		str1 = l[1]
		str1 = str1[::-1]
		j = 0
		while j < len(str1) and str1[j] == '1':
			j += 1
		if j == len(str1):
			flag[1] = True
		if not flag[1]:
			count = count + str1[j:].count('1') + l[1].count('1') * (l[3] - 1) + l[0].count('1')
		elif flag[1]:
			str0 = l[0]
			str0 = str0[::-1]
			k = 0
			while k < len(str0) and str0[k] == '1':
				k += 1
			if k == len(str0):
				flag[0] = True
			if not flag[0]:
				count = count + str0[k:].count('1')
			elif flag[0]:
				count = count
	print(count)


t = int(input())
while t:
	(a, b, c, d) = input().split()
	d = int(d)
	an = a.count('1') + b.count('1') * d + c.count('1')
	lc = len(c)
	lb = len(b)
	la = len(a)
	cc = 0
	cb = 0
	ca = 0
	for i in range(lc - 1, -1, -1):
		if c[i] == '0':
			break
		else:
			cc += 1
	if cc == lc:
		for i in range(lb - 1, -1, -1):
			if b[i] == '0':
				break
			else:
				cb += 1
		if cb == lb:
			for i in range(la - 1, -1, -1):
				if a[i] == '0':
					break
				else:
					ca += 1
			if ca == la:
				print(1)
			else:
				print(an - cc - cb * d - (ca - 1))
		else:
			print(an - cc - (cb - 1))
	else:
		print(an - (cc - 1))
	t = t - 1


t = int(input())
while t > 0:
	l = ['', '', '']
	c = 1
	(l1, l2, l3, n) = input().split(' ')
	n = int(n)
	(a1, b1, c1) = (l1.count('1'), l2.count('1'), l3.count('1'))
	(a0, b0, c0) = (l1.count('0'), l2.count('0'), l3.count('0'))
	if c0 == 0:
		if b0 == 0:
			if a0 == 0:
				print(1)
			else:
				i = len(l1) - 1
				while i >= 0 and l1[i] == '1':
					i = i - 1
				while i >= 0:
					if l1[i] == '1':
						c = c + 1
					i = i - 1
				print(c)
		else:
			i = len(l2) - 1
			while i >= 0 and l2[i] == '1':
				i = i - 1
			while i >= 0:
				if l2[i] == '1':
					c = c + 1
				i = i - 1
			print(c + a1 + b1 * (n - 1))
	else:
		i = len(l3) - 1
		while i >= 0 and l3[i] == '1':
			i = i - 1
		while i >= 0:
			if l3[i] == '1':
				c = c + 1
			i = i - 1
		print(c + a1 + b1 * n)
	t = t - 1


t = int(input())
ans = []
for i in range(t):
	ip = list(input().split(' '))
	l1 = ip[0]
	l2 = ip[1]
	l3 = ip[2]
	n = int(ip[3])
	zero_flag = 0
	count = 0
	rep_count = 0
	for j in range(len(l3) - 1, -1, -1):
		if l3[j] == '1':
			count += 1
			if zero_flag == 0:
				rep_count += 1
		else:
			zero_flag = 1
	l2_count = 0
	l2_rep_count = 0
	zero_flag = 0
	for j in range(len(l2) - 1, -1, -1):
		if l2[j] == '1':
			l2_count += 1
			if zero_flag == 0:
				l2_rep_count += 1
		else:
			zero_flag = 1
	l1_count = 0
	l1_rep_count = 0
	zero_flag = 0
	for j in range(len(l1) - 1, -1, -1):
		if l1[j] == '1':
			l1_count += 1
			if zero_flag == 0:
				l1_rep_count += 1
		else:
			zero_flag = 1
	if rep_count == len(l3):
		if l2_rep_count == len(l2):
			rep_count += l2_rep_count * n + l1_rep_count
		else:
			rep_count += l2_rep_count
	count += l2_count * n + l1_count
	count -= rep_count
	ans.append(count + 1)
for x in ans:
	print(x)


def returnIndexAfterContinuousOnes(s):
	l = len(s)
	i = l - 1
	while i >= 0 and s[i] == '1':
		i -= 1
	return i

def returnCountOfOnes(s, j):
	i = j
	sum = 0
	while i >= 0:
		if s[i] == '1':
			sum += 1
		i -= 1
	return sum
t = int(input())
for xyz in range(t):
	inp = str(input()).split()
	l1 = inp[0]
	l2 = inp[1]
	l3 = inp[2]
	n = int(inp[3])
	len3 = len(l3)
	i = len3 - 1
	ans = 1
	chk = returnIndexAfterContinuousOnes(l3)
	if chk == -1:
		chk = returnIndexAfterContinuousOnes(l2)
		if chk == -1:
			chk = returnIndexAfterContinuousOnes(l1)
			if chk == -1:
				ans += 0
			else:
				ans += returnCountOfOnes(l1, chk)
		else:
			ans += returnCountOfOnes(l2, chk) + returnCountOfOnes(l2, len(l2) - 1) * (n - 1) + returnCountOfOnes(l1, len(l1) - 1)
	else:
		ans += returnCountOfOnes(l3, chk) + returnCountOfOnes(l2, len(l2) - 1) * n + returnCountOfOnes(l1, len(l1) - 1)
	print(ans)


for i in range(0, int(input())):
	lst = [i for i in input().split()]
	(s1, s2, s3, n) = (lst[0], lst[1], lst[2], int(lst[3]))
	o = 0
	for i in s1:
		if i == '1':
			o += 1
	for i in s2:
		if i == '1':
			o += n
	for i in s3:
		if i == '1':
			o += 1
	o += 1
	l = len(s3) - 1
	if s3[l] == '1':
		while l >= 0 and s3[l] == '1':
			l -= 1
			o -= 1
		if l == -1:
			l = len(s2) - 1
			k = 0
			while l >= 0 and s2[l] == '1':
				l -= 1
				k += 1
			if k == len(s2):
				o -= n * len(s2)
			else:
				o -= k
			if l == -1:
				l = len(s1) - 1
				while l >= 0 and s1[l] == '1':
					l -= 1
					o -= 1
	print(o)


import sys

def ones(x):
	return sum((1 for c in list(x) if c == '1'))

def trailones(x):
	ret = 0
	for c in reversed(list(x)):
		if c == '0':
			break
		ret += 1
	return ret

def solve(a, b, c, d):
	oc = ones(c)
	tc = trailones(c)
	if tc < len(c):
		return ones(a) + ones(b) * d + oc - tc + 1
	tb = trailones(b)
	if tb < len(b):
		return ones(a) + ones(b) * d - tb + 1
	return ones(a) - trailones(a) + 1
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(a, b, c, d) = f.readline().split()
	d = int(d)
	print(solve(a, b, c, d))


for _ in range(int(input())):
	(a, b, c, n) = map(str, input().split())
	n = int(n)
	s = a + b + c
	c1 = a.count('1') + n * b.count('1') + c.count('1')
	l = len(s)
	i = l - 1
	while i >= 0:
		if s[i] == '0':
			break
		i -= 1
	if i == l - 1:
		print(c1 + 1)
	elif i == -1:
		print(1)
	elif i <= len(a) - 1:
		print(c1 - (len(a) - i - 1) + 1 - (n * b.count('1') + c.count('1')))
	else:
		print(c1 - (l - i - 1) + 1)


t = int(input())
for t0 in range(t):
	(l1, l2, l3, n) = [i for i in input().strip().split()]
	n = int(n)
	s = 0
	s1 = 0
	if '0' in l3:
		r1 = l3.rindex('0')
		s = l1.count('1') + l2.count('1') * n + l3[0:r1].count('1') + 1
	elif '0' in l2:
		r1 = l2.rindex('0')
		ct = l2[r1:].count('1')
		s = l1.count('1') + l2.count('1') * n + 1 - ct
	elif '0' in l1:
		r1 = l1.rindex('0')
		ct = l1[r1:].count('1')
		s = l1.count('1') + 1 - ct
	else:
		s = 1
	print(s)