Limak is a little polar bear.
He is playing a video game and he needs your help.
There is a row with N cells, each either empty or occupied by a soldier, denoted by '0' and '1' respectively.
The goal of the game is to move all soldiers to the right (they should occupy some number of rightmost cells).
The only possible command is choosing a soldier and telling him to move to the right as far as possible.
Choosing a soldier takes 1 second, and a soldier moves with the speed of a cell per second.
The soldier stops immediately if he is in the last cell of the row or the next cell is already occupied.
Limak isn't allowed to choose a soldier that can't move at all (the chosen soldier must move at least one cell to the right).
Limak enjoys this game very much and wants to play as long as possible.
In particular, he doesn't start a new command while the previously chosen soldier moves.
Can you tell him, how many seconds he can play at most?

-----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 a string S describing the row with N cells.
Each character is either '0' or '1', denoting an empty cell or a cell with a soldier respectively.

-----Output-----
For each test case, output a single line containing one integer — the maximum possible number of seconds Limak will play the game.

-----Constraints-----
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 105 (N denotes the length of the string S)

-----Subtasks-----
- Subtask #1 (25 points): 1 ≤ N ≤ 10
- Subtask #2 (25 points): 1 ≤ N ≤ 2000
- Subtask #3 (50 points): Original constraints.

-----Example-----
Input:
4
10100
1100001
000000000111
001110100011010

Output:
8
10
0
48

-----Explanation-----
Test case 1.
The initial string is 10100.
There are N = 5 cells.
There is one soldier in the first cell, and one soldier in the third cell.
The following scenario maximizes the total time:
- Limak chooses the soldier in the first cell.
This soldier can move only one cell to the right.
It takes 1 second to choose a soldier and 1 second for a soldier to move to the next cell (2 seconds in total).
The string is 01100 now.
- Limak has only one choice.
He must choose the soldier in the third cell because the other soldier can't move at all (the soldier in the second cell can't move to the right because the next cell is already occupied).
Choosing a soldier takes 1 second.
The chosen soldier moves from the third cell to the fifth cell, which takes 2 seconds.
This operation takes 1 + 2 = 3 seconds in total.
The string is 01001 now.
- Limak has only one choice again.
Since the soldier in the last row can't move further to the right, the soldier in the second cell must be chosen.
He will move 2 cells to the right.
This operation takes 1 + 2 = 3 seconds in total.
The string become 00011 and the game is over.
The total time is 2 + 3 + 3 = 8.
Test case 2.
The initial string is 1100001.
There is only one possible scenario:
- 1100001 is changed to 1000011 in 5 seconds (1 second to choose a soldier and 4 seconds for the soldier to move 4 cells to the right).
- 1000011 is changed to 0000111 in 5 seconds.

The total time is 5 + 5 = 10 seconds.
Test case 3.
The game is over immediately because all soldiers occupy rightmost cells already.
The answer is 0.

Difficulty: MEDIUM_HARD
Tags: Range queries
Skill types: Range queries

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	time = 0
	s = list(map(int, input().lstrip('0')))
	ones = 0
	zeroes = 0
	i = 0
	while i < len(s):
		if i < len(s):
			while s[i] == 1:
				i += 1
				ones += 1
				if i >= len(s):
					break
		if i < len(s):
			while s[i] == 0:
				i += 1
				zeroes += 1
				if i >= len(s):
					break
		time += ones * (zeroes + 1)
		zeroes = 0
	if len(s) > 0:
		if s[-1] == 1:
			time -= s.count(1)
	print(time)


t = int(input())
while t:
	s = input()
	n = len(s)
	if s[n - 1] == '1':
		n -= 1
	ans = 0
	count = 0
	i = n - 1
	while i >= 0:
		if s[i] == '0':
			count += 1
		else:
			count += 1
			if s[i + 1] == '1':
				count -= 1
			ans += count
		i -= 1
	print(ans)
	t -= 1


import sys
import itertools

def get_group_list(row):
	group_size = 0
	grouped_row = []
	for i in row:
		if i == 0:
			grouped_row.append(group_size)
			group_size = 0
			grouped_row.append(i)
		elif i == 1:
			group_size += 1
	return list(filter(lambda x: x > 0, grouped_row))

def get_distance_list(row):
	zeroes = 0
	total = 0
	for i in reversed(row):
		if i == 0:
			zeroes += 1
		elif i == 1:
			total += zeroes
	return total

def grouping_method(row):
	distance_sum = get_distance_list(row)
	group_list = get_group_list(row)
	total_group_sum = 0
	for (i, group) in enumerate(reversed(group_list), start=1):
		total_group_sum += i * group
	return distance_sum + total_group_sum
test_cases = int(sys.stdin.readline().strip())
for test in range(test_cases):
	row = [int(i) for i in sys.stdin.readline().strip()]
	seconds = grouping_method(row)
	print(seconds)


T = int(input())
ans = []
for _ in range(T):
	S = input()
	N = len(S)
	ones = 0
	count = 0
	for i in range(N - 1, -1, -1):
		if S[i] == '1':
			count += N - i - 1 - ones
			ones += 1
	t = S.split('0')
	group = 1
	for i in range(len(t) - 1, -1, -1):
		if i != len(t) - 1 and '1' in t[i]:
			count += len(t[i]) * group
			group += 1
	ans.append(count)
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	s = input()
	pre = []
	n = len(s)
	j = 0
	ss = {}
	for i in range(n):
		if s[i] == '1':
			pre.append(i)
			ss[i] = j
			j += 1
	pre.append(n)
	suff = [0 for i in range(n + 1)]
	tot = 0
	duff = [0 for i in range(n + 1)]
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			pass
		else:
			suff[i] = suff[pre[ss[i] + 1]] + max(tot, 0)
			duff[i] = max(tot, 0)
			tot -= 1
		tot += 1
	tot = 0
	st = False
	dp = [0] * (n + 1)
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			st = True
			continue
		else:
			if st:
				tot += 1
				st = False
			dp[i] = tot + dp[pre[ss[i] + 1]]
	print(suff[pre[0]] + dp[pre[0]])


for _ in range(int(input())):
	a = list(input())
	n = len(a)
	for i in reversed(range(n)):
		if a[i] == '1':
			a.pop()
		else:
			break
	n = len(a)
	zero = 0
	prev = tot = 0
	c = 0
	for i in reversed(range(n)):
		if a[i] == '0':
			zero += 1
			continue
		if prev != zero:
			prev = zero
			c += 1
		tot += c + zero
	print(tot)


t = int(input())
for t0 in range(t):
	str1 = str(input())
	list1 = []
	for i in str1:
		list1.append(int(i))
	lis2 = []
	lis3 = []
	list2 = []
	c = 0
	for j in list1:
		if j == 1:
			list2.append(c)
		c += 1
	sum1 = 0
	for j in range(1, len(list2)):
		if list2[j] - list2[j - 1] > 1:
			sum1 += j + j * (list2[j] - list2[j - 1] - 1)
	if len(list2) > 0:
		if len(list1) - 1 > list2[-1]:
			sum1 += len(list2) + len(list2) * (len(list1) - 1 - list2[-1])
	print(sum1)


for _ in range(int(input())):
	s = list(input())
	score = 0
	ones = 0
	consz = 0
	for i in range(len(s)):
		if i < len(s) - 1:
			if s[i] == '0' and s[i + 1] == '1':
				score += ones * (consz + 2)
				consz = 0
			elif s[i] == '1':
				ones += 1
			elif s[i] == '0':
				consz += 1
		elif s[i] == '0':
			score += ones * (consz + 2)
	print(score)


import sys
for _ in range(int(input())):
	s = str(input())
	arr = [int(i) for i in s]
	n = len(arr)
	total = 0
	cnt = 0
	(lstindx, curr) = (n - 1, n - 1)
	while arr[curr] == 1 and curr >= 0:
		curr -= 1
		lstindx -= 1
	while curr >= 0:
		if arr[curr] == 1:
			if arr[curr + 1] == 0:
				cnt += 1
			total += cnt + (lstindx - curr)
			lstindx -= 1
		curr -= 1
	print(total)


for _ in range(int(input())):
	arr = list(input())
	n = len(arr)
	for i in reversed(range(n)):
		if arr[i] == '1':
			arr.pop()
		else:
			break
	n = len(arr)
	zero = prev = total = cnt = 0
	for i in reversed(range(n)):
		if arr[i] == '0':
			zero += 1
			continue
		if prev != zero:
			prev = zero
			cnt += 1
		total += cnt + zero
	print(total)


for _ in range(int(input())):
	animal = input()
	answer = 0
	cer = 0
	sqwerty = 0
	po = 0
	for lk in range(2):
		po += 1
	for lk in range(2):
		po += 1
	for de in range(2):
		if de != 0:
			po += 1
	for i in range(len(animal)):
		if animal[i] == '1':
			answer += sqwerty * cer
			cer += 1
			for lk in range(2):
				po += 1
			for lk in range(2):
				po += 1
			for de in range(2):
				if de != 0:
					po += 1
			sqwerty = 0
		elif cer != 0:
			if sqwerty == 0:
				sqwerty = 1
			sqwerty += 1
	for lk in range(2):
		po += 1
	for lk in range(2):
		po += 1
	for de in range(2):
		if de != 0:
			po += 1
	if animal[len(animal) - 1] == '0':
		answer += sqwerty * cer
	print(answer)


for I in range(int(input())):
	s = str(input())
	soldier_number = 0
	ans = 0
	i = 0
	while i < len(s):
		if s[i] == '1':
			soldier_number += 1
			i += 1
		else:
			zero_number = 0
			while i < len(s) and s[i] == '0':
				zero_number += 1
				i += 1
			ans += soldier_number * (zero_number + 1)
	print(ans)


for _ in range(int(input())):
	row = [i for i in input()]
	(L, ans, pos) = (len(row), 0, -1)
	cnt = [0] * L
	if row[L - 1] == '0':
		cnt[L - 1] = 1
	for i in range(L - 2, -1, -1):
		cnt[i] = cnt[i + 1]
		if row[i] == '0' and row[i + 1] == '1':
			cnt[i] += 1
	for i in range(L - 1, -1, -1):
		if row[i] == '0':
			pos = i
			break
	for i in range(pos - 1, -1, -1):
		if row[i] == '1':
			(ans, pos) = (ans + pos - i + cnt[i], pos - 1)
	print(ans)


t = int(input())
for i in range(t):
	one = 0
	sec = 0
	given = input()
	given = given[given.find('1'):]
	while True:
		if not '0' in given:
			break
		index0 = given.find('0')
		one += index0
		given = given[index0:]
		if not '1' in given:
			zero = len(given)
			sec += one * (zero + 1)
			break
		index1 = given.find('1')
		zero = index1
		sec += one * (zero + 1)
		given = given[index1:]
	print(sec)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	i = n - 1
	ones = s.count('1')
	c = 0
	ans = 0
	while i >= 0:
		if s[i] == '0':
			c += 1
			i -= 1
		else:
			if c:
				ans += ones * (c + 1)
				c = 0
			while i >= 0 and s[i] == '1':
				ones -= 1
				i -= 1
	print(ans)


from sys import stdin

def solve():
	T = int(stdin.readline().strip())
	for t in range(T):
		game = stdin.readline().strip()
		game = list(game)
		length = len(game)
		cnt = ans = 0
		first = True
		start = end = -1
		i = 0
		while i < length:
			if game[i] == '1':
				cnt += 1
				if first:
					start = i
					first = False
				else:
					end = i
			if start != -1 and end != -1 and (start + cnt != length) and (start + cnt - 1 != end):
				if cnt > 1:
					ans += (end - start - cnt + 1) * (cnt - 1) + (cnt - 1)
				else:
					ans += (end - start - cnt + 1) * cnt + (cnt - 1)
				start = end - cnt + 1
				end = -1
				first = False
			i += 1
		if start + cnt != length:
			ans += (length - start - cnt + 1) * cnt
		print(ans)
solve()


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)) + '\n')

def main():
	for _ in tr():
		cells = line() + '1'
		soldiers = 0
		n = len(cells)
		count = 0
		prev_soldier = False
		soldier_index = 0
		last_cell_index = 0
		for i in range(n):
			if cells[i] == '1':
				if not prev_soldier:
					count += soldiers * (last_cell_index - soldier_index) + soldiers
				soldier_index = i + 1
				soldiers += 1
				prev_soldier = True
			else:
				prev_soldier = False
				last_cell_index = i + 1
		print(count)
main()


T = int(input())
for i in range(T):
	data = [x.strip() for x in input()]
	cnt = 0
	los = len(data) - 1
	f = -1
	zf = -1
	pc = [0] * (los + 1)
	cost = 0
	for i2 in range(los, -1, -1):
		if data[i2] == '0' and zf == -1:
			zf += 1
		if data[i2] == '1' and f == -1 and (i != los) and (zf != -1):
			pc[i2] = 1
			f += 1
			frontC = 1
		elif data[i2] == '1' and (not f == -1):
			if data[i2 + 1] == '1':
				pc[i2] = frontC
			else:
				pc[i2] = frontC + 1
				frontC = pc[i2]
	f = -1
	for i2 in range(los, -1, -1):
		if f == -1 and data[i2] == '0':
			moveTo = i2
			f += 1
		elif data[i2] == '1' and f != -1:
			data[moveTo] = '1'
			data[i2] = '0'
			cost += moveTo - i2
			moveTo -= 1
	for i2 in range(0, los):
		cost += int(pc[i2])
	print(cost)


t = int(input())
for i in range(t):
	n = input()
	l = list(n)
	one = 0
	sec = 0
	zero = 0
	k = 0
	f = 0
	while l[k] == '0':
		k = k + 1
		if k == len(l):
			break
	for j in range(k, len(l)):
		if l[j] == '1':
			if f == 1:
				sec = sec + one + one * zero
				f = 0
			zero = 0
			one = one + 1
		if l[j] == '0':
			zero = zero + 1
			f = 1
	if not zero == 0:
		sec = sec + one + one * zero
	print(sec)


for _ in range(int(input())):
	s = input()
	count = 0
	n = len(s)
	count = 0
	total = 0
	lastindex = n - 1
	curr = n - 1
	while curr >= 0 and s[lastindex] == '1':
		curr -= 1
		lastindex -= 1
	while curr >= 0:
		if s[curr] == '1':
			if s[curr + 1] == '0':
				count += 1
			total += count + (lastindex - curr)
			lastindex -= 1
		curr -= 1
	print(total)


from itertools import groupby
for i in range(int(input())):
	ls = []
	N = input()
	k = 0
	for (i, j) in groupby(N):
		ls.append(list(j))
	sum = 0
	temp = 0
	for i in range(len(ls)):
		if ls[i][0] == '1':
			temp += len(ls[i])
			if i != len(ls) - 1:
				sum += temp * (len(ls[i + 1]) + 1)
	print(sum)


t = int(input())
for i in range(t):
	s = input()
	s = s + '1'
	c = 0
	one = 0
	j = 0
	while True:
		if s[j] == '1':
			one += 1
			ind = s.index('1', j + 1)
			if ind - j == 1:
				j += 1
				if j == len(s) - 1:
					break
				continue
			else:
				c += one * (ind - j)
		j += 1
		if j == len(s) - 1:
			break
	print(c)


T = int(input())
n = 1
while n <= T:
	st = str(input())
	d = {}
	ones = 1
	for i in range(len(st)):
		if st[i] == '1':
			d[i] = ones
			ones += 1
	i = 0
	time = 0
	pos = len(st)
	for pos in sorted(d):
		if i == 0:
			ppos = pos
			i = 1
			continue
		if ppos + 1 != pos:
			time = time + d[ppos] * (pos - ppos - 1) + d[ppos]
		ppos = pos
	if pos < len(st) - 1:
		time = time + d[pos] * (len(st) - pos - 1) + d[pos]
	print(time)
	n += 1


for x in range(int(input())):
	rawinput = input()
	soldiers = 0
	moves = 0
	end = len(rawinput) - 1
	if rawinput[len(rawinput) - 1] == '1':
		while end >= 0:
			if rawinput[end] != '1' or (rawinput[end] == '1' and end == 0):
				index = end - 1
				last = end
				break
			end -= 1
	else:
		index = end - 1
		last = end
	while index >= 0:
		if rawinput[index] == '1':
			moves += last - index + 1
			moves += soldiers
			last -= 1
			if index - 1 >= 0 and rawinput[index - 1] != '1':
				soldiers += 1
		index -= 1
	print(moves)


for i in range(int(input())):
	s = input()
	n = len(s)
	arr = [0] * n
	for i in range(n):
		arr[i] = int(s[i])
	total = 0
	count = 0
	lastIdx = n - 1
	curr = n - 1
	while arr[curr] == 1 and curr >= 0:
		lastIdx -= 1
		curr -= 1
	while curr >= 0:
		if arr[curr] == 1:
			if arr[curr + 1] == 0:
				count += 1
			total += count + (lastIdx - curr)
			lastIdx -= 1
		curr -= 1
	print(total)


for _ in range(int(input())):
	l = list(map(int, input().strip()))
	for i in range(len(l) - 1, -1, -1):
		if l[i] == 1:
			l.pop()
		else:
			break
	if l.count(1):
		(time, prev, z, c) = (0, 0, 0, 0)
		for i in range(len(l) - 1, -1, -1):
			if l[i] == 0:
				z += 1
				continue
			if prev != z:
				prev = z
				c += 1
			time += c + z
		print(time)
	else:
		print(0)


n = int(input())
while n:
	n -= 1
	str_val = input()
	final_place = len(str_val) - 1
	size = len(str_val)
	jumps = 0
	ans = 0
	for i in range(size - 1, -1, -1):
		if str_val[i] == '1':
			if i != size - 1 and str_val[i + 1] == '0':
				jumps += 1
			ans += jumps + (final_place - i)
			final_place -= 1
	print(ans)


t = int(input())
for i in range(0, t):
	enc = 0
	jump = -1
	total = flag = 0
	sel = 0
	string = input()
	n = len(string)
	i = n - 1
	while (i >= 0) & (string[i] == '1'):
		i -= 1
		enc += 1
	while i >= 0:
		if (string[i] == '1') & (flag == 0):
			jump += 1
			flag = 1
			sel = n - 1 - enc - i
			total += jump + sel + 1
			enc += 1
		elif string[i] == '0':
			flag = 0
			sel = 1
		else:
			sel = n - 1 - enc - i
			total += jump + sel + 1
			enc += 1
		i -= 1
	print(total)


for x in range(int(input())):
	a = [int(i) for i in input()]
	a.append(1)
	su = 0
	b = []
	for i in a:
		if i == 1:
			su += 1
		b.append(su)
	hh = 0
	cu = 0
	for i in range(len(b)):
		if a[i] == 0:
			cu += 1
		elif cu != 0:
			hh += (cu + 1) * b[i - 1]
			cu = 0
	print(hh)


for _ in range(int(input())):
	string = list(input())
	time = 0
	n = string.count('1')
	k = len(string)
	for _ in range(n):
		for i in range(k):
			if string[i] == '1':
				if i == k - 1:
					break
				j = i + 1
				while string[j] != '1':
					string[j - 1] = '0'
					string[j] = '1'
					if j - i == 1:
						time += 1
					time += 1
					if j < k - 1:
						j += 1
	print(time)


casos = int(input())
ejecuciones = 0
respuestas = []
soldados = 0
pasos = 0
tiempoIteracion = 0
total = 0
while ejecuciones < casos:
	entrada = input()
	for soldado in entrada:
		if soldado == '0':
			pasos += 1
		else:
			if pasos > 0:
				tiempoIteracion = soldados + soldados * pasos
				total += tiempoIteracion
				pasos = 0
			soldados += 1
	if pasos > 0:
		total += soldados + soldados * pasos
	respuestas.append(total)
	ejecuciones += 1
	soldados = 0
	pasos = 0
	tiempoIteracion = 0
	total = 0
for res in respuestas:
	print(str(res))


def solve():
	T = int(input())
	for t in range(T):
		game = input()
		game = list(game)
		length = len(game)
		cnt = ans = 0
		first = True
		start = end = -1
		i = 0
		while i < length:
			if game[i] == '1':
				cnt += 1
				if first:
					start = i
					first = False
				else:
					end = i
			if start != -1 and end != -1 and (start + cnt != length) and (start + cnt - 1 != end):
				if cnt > 1:
					ans += (end - start - cnt + 1) * (cnt - 1) + (cnt - 1)
				else:
					ans += (end - start - cnt + 1) * cnt + (cnt - 1)
				start = end - cnt + 1
				end = -1
				first = False
			i += 1
		if start + cnt != length:
			ans += (length - start - cnt + 1) * cnt
		print(ans)
solve()


t = int(input())
for T in range(0, t):
	str = input()
	a = []
	for i in range(0, len(str) - 1):
		if str[i] == '1':
			c = 0
			j = i + 1
			while str[j] == '0':
				c += 1
				if j < len(str) - 1:
					j += 1
				else:
					break
			a.append(c + 1)
	tot = 0
	for i in range(0, len(a)):
		if a[i] != 1:
			tot += a[i] * (i + 1)
	print(tot)


def soln(s):
	n = len(s)
	res = ones = i = 0
	while i < n and s[i] != '1':
		i += 1
	while i < n:
		while i < n and s[i] == '1':
			ones += 1
			i += 1
		zeros = 0
		while i < n and s[i] == '0':
			zeros += 1
			i += 1
		if zeros == 0:
			continue
		res += ones * (zeros + 1)
	return res
for _ in range(int(input())):
	s = input()
	print(soln(s))


test = int(input())
while test:
	count = 1
	ans = 0
	n = input()
	leng = len(n)
	while n[leng - 1] == '1':
		leng -= 1
		if leng == 0:
			break
	for i in range(leng):
		if n[leng - i - 1] == '0':
			count += 1
		else:
			if n[leng - i] == '1':
				count -= 1
			ans += count
			count += 1
	print(ans)
	test -= 1


t = int(input())
ans = []
for i in range(t):
	s = input()
	n = len(s)
	o = 0
	c = 0
	for j in range(n - 1, -1, -1):
		if s[j] == '1':
			c += n - j - 1 - o
			o += 1
	x = s.split('0')
	g = 1
	for k in range(len(x) - 1, -1, -1):
		if k != len(x) - 1 and '1' in x[k]:
			c += len(x[k]) * g
			g += 1
	ans.append(c)
for i in ans:
	print(i)


t = int(input())
while t:
	t -= 1
	s = input()[::-1]
	zeroes = 0
	zero_batches = 0
	result = 0
	last = -1
	for i in s:
		if '0' == i:
			zeroes += 1
		if '1' == i:
			if '0' == last:
				zero_batches += 1
			result += zeroes
			result += zero_batches
		last = i
	print(result)


for xaxa in range(int(input())):
	o = 0
	m = 0
	s = input()
	n = len(s)
	for i in range(n):
		c = s[i]
		if c == '1':
			o += 1
		else:
			m += o
			if i < n - 1 and s[i + 1] == '1':
				m += o
	if s[-1] == '0':
		m += o
	print(m)


def solve():
	s = input()
	n = len(s)
	ans = 0
	cnt = 0
	selected = False
	for i in range(n):
		if s[i] == '0':
			ans += cnt
			if not selected:
				selected = True
				ans += cnt
		else:
			cnt += 1
			selected = False
	print(ans)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	s = input() + ' '
	(output, zeroes, ones) = (0, 0, 0)
	for i in range(len(s)):
		if (s[i] == '1' or s[i] == ' ') and zeroes >= 1:
			output += ones * (zeroes + 1)
			zeroes = 0
			ones += 1
		elif s[i] == '1':
			ones += 1
		elif s[i] == '0':
			zeroes += 1
	print(output)


t = int(input())
for q in range(t):
	arr = input()
	arr = list(arr)
	arr_len = len(arr)
	count_time = 0
	num_zeroes = 0
	num_ones = 0
	num_ones_total = 0
	multiplier = 0
	num_selections = 0
	flag = 0
	for i in arr:
		if i == '1':
			num_ones_total += 1
			multiplier += 1
			flag += 1
		else:
			num_ones = num_ones_total
			num_zeroes += multiplier
			if flag != 0:
				num_selections += num_ones
				flag = 0
	count_time = num_selections + num_zeroes
	print(count_time)


import bisect
T = int(input())
for testCaseID in range(T):
	cellMap = input()
	soldierList = []
	gapCounter = 0
	for i in range(len(cellMap)):
		if cellMap[i] == '1':
			if len(soldierList) > 0:
				soldierList[-1] = gapCounter
			soldierList.append(0)
			gapCounter = 0
		else:
			gapCounter += 1
	if len(soldierList) > 0:
		soldierList[-1] = gapCounter
	timer = 0
	for index in range(len(soldierList)):
		if soldierList[index] > 0:
			timer += (1 + soldierList[index]) * (index + 1)
	print(timer)


for t in range(int(input())):
	s = input()[::-1].strip()
	last = 0
	extra_stops = 0
	try:
		for i in range(s.index('01') + 2, len(s)):
			if s[i] == '1':
				if s[i - 1] == '0':
					last += 1
				extra_stops += last
	except ValueError:
		pass
	ans = 0
	ones = 0
	for i in range(len(s)):
		if s[i] == '1':
			ones += 1
			this = i - ones + 2
			if this > 1:
				ans += this
	print(ans + extra_stops)


T = int(input())
for t in range(T):
	string = input()
	ones = 0
	dists = []
	first = True
	dist = 1
	for c in reversed(string):
		if c == '1':
			dists.append(dist)
			dist = 1
			ones += 1
		else:
			dist += 1
	sums = 0
	for (i, dist) in enumerate(dists):
		if dist > 1:
			sums += dist * (ones - i)
	print(sums)


def rowsold():
	T = int(input())
	for _ in range(T):
		count1 = 0
		sec = 0
		flag = 0
		l = [int(d) for d in str(input())]
		for i in range(len(l)):
			if l[i] == 1:
				count1 += 1
				flag = 1
			elif l[i - 1] == 1 and l[i] == 0:
				sec = sec + count1 * 2
			elif l[i - 1] == 0 and l[i] == 0 and (flag == 1):
				sec = sec + count1
		print(sec)
rowsold()


t = int(input())
while t > 0:
	t -= 1
	s = input()
	ls = len(s)
	c = 0
	tot = 0
	i = 0
	l = []
	while i < ls:
		k = 0
		if s[i] == '0':
			while i + 1 < ls and s[i + 1] == '0':
				i += 1
				k += 1
			l.append(k + 1)
		else:
			l.append(-1)
		i += 1
	ll = len(l)
	i = 0
	while i < ll:
		if l[i] != -1:
			tot += (1 + l[i]) * c
		else:
			c += 1
		i += 1
	print(tot)


for _ in range(int(input())):
	s = input()
	c = 0
	n = len(s)
	c = 0
	m = 0
	r = n - 1
	curr = n - 1
	while curr >= 0 and s[r] == '1':
		curr -= 1
		r -= 1
	while curr >= 0:
		if s[curr] == '1':
			if s[curr + 1] == '0':
				c += 1
			m += c + (r - curr)
			r -= 1
		curr -= 1
	print(m)


t = int(input().strip())
for a0 in range(t):
	n = input().strip()
	pos_ones = [len(n) - (i + 1) for i in range(len(n)) if n[i] == '1']
	len_one = len(pos_ones)
	pos_ones.reverse()
	i = 0
	total_cnt = 0
	while i < len_one:
		if pos_ones[i] == i:
			i += 1
		else:
			if i == 0:
				total_cnt += (pos_ones[i] + 1) * (len_one - i)
			elif pos_ones[i] - pos_ones[i - 1] > 1:
				total_cnt += (pos_ones[i] - pos_ones[i - 1]) * (len_one - i)
			i += 1
	print(total_cnt)


def find_1seq(S, start):
	i = start
	while i < len(S) and S[i] == '0':
		i += 1
	j = i + 1
	while j < len(S) and S[j] == '1':
		j += 1
	return (j - i, j)
for _ in range(int(input())):
	S = input()
	time = 0
	i = 0
	prev_nbr_ones = 0
	while True:
		(nbr_ones, i) = find_1seq(S, i)
		nbr_ones += prev_nbr_ones
		prev_nbr_ones = nbr_ones
		if i < len(S):
			time += nbr_ones
			while i < len(S) and S[i] == '0':
				time += nbr_ones
				i += 1
		else:
			break
	print(time)


for _ in range(int(input())):
	s = input()
	obstacles = 0
	jumps = 0
	end = len(s) - 1
	if s[len(s) - 1] == '1':
		while end >= 0:
			if s[end] != '1' or (s[end] == '1' and end == 0):
				index = end - 1
				last = end
				break
			end -= 1
	else:
		index = end - 1
		last = end
	while index >= 0:
		if s[index] == '1':
			jumps += last - index + 1
			jumps += obstacles
			last -= 1
			if index - 1 >= 0 and s[index - 1] != '1':
				obstacles += 1
		index -= 1
	print(jumps)


try:
	t = int(input())
	while t > 0:
		t -= 1
		s = input()
		intermediate = 0
		count = 0
		end = len(s) - 1
		if s[len(s) - 1] == '1':
			while end >= 0:
				if s[end] != '1' or (s[end] == '1' and end == 0):
					pos = end - 1
					last = end
					break
				end -= 1
		else:
			pos = end - 1
			last = end
		while pos >= 0:
			if s[pos] == '1':
				count = count + (last - pos) + intermediate + 1
				last -= 1
				if pos - 1 >= 0 and s[pos - 1] != '1':
					intermediate += 1
			pos -= 1
		print(count)
except EOFError:
	pass


t = int(input())
for each in range(t):
	a = input()
	n = len(a)
	picks = [0] * (n + 1)
	picks[n - 1] = 1 if a[n - 1] == '0' else 0
	i = n - 2
	while i > -1:
		picks[i] = picks[i + 1]
		if a[i] == '0' and a[i + 1] == '1':
			picks[i] += 1
		i -= 1
	disp = [0] * (n + 1)
	soldiers = 0
	i = n - 1
	while i > -1:
		if a[i] == '1':
			disp[i] = n - soldiers - 1 - i
			soldiers += 1
		i -= 1
	ans = 0
	for i in range(n):
		if a[i] == '1':
			ans += picks[i] + disp[i]
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	i = 0
	ans = 0
	n1 = 0
	while i < n:
		if s[i] == '1':
			i += 1
			n1 += 1
			while i < n and s[i] == '1':
				i += 1
				n1 += 1
			n0 = 0
			while i < n and s[i] == '0':
				i += 1
				n0 += 1
			if n0 != 0:
				ans += (n0 + 1) * n1
		else:
			i += 1
	print(ans)


t = int(input())
for y in range(t):
	s = list(map(int, list(input())))
	b = a = ans = 0
	z = 0
	ek = -1
	for x in range(len(s)):
		if s[x] == 1 and a != 0:
			ans = ans + b * (a + 1)
			ek = 1
			a = 0
			z = 1
		if s[x] == 1 and ek == 1:
			b += 1
			z = 1
		if s[x] == 1 and z != 1:
			ek = b = 1
		if s[x] == 0 and ek == 1:
			a += 1
	if s[x] == 0 and x == len(s) - 1:
		ans = ans + b * (a + 1)
	print(ans)


h = int(input())
for k in range(0, h):
	s = input()
	l = len(s)
	counter0 = 0
	counter1 = 0
	value = 0
	for i in range(0, l):
		if i == l - 1 and s[l - 1] == '0':
			counter0 += 1
			value += counter0 * counter1 + counter1
		elif s[i] == '0':
			counter0 += 1
		else:
			if s[i - 1] == '0':
				value += counter0 * counter1 + counter1
				counter0 = 0
			counter1 += 1
	print(value)


t = input()
for i in range(int(t)):
	n = input()
	l = len(n)
	time = 0
	count1 = 0
	j = 0
	while j < l:
		count0 = 0
		while j < l and n[j] == '1':
			count1 += 1
			j += 1
		while j < l and n[j] == '0':
			count0 += 1
			j += 1
		if j < l or n[j - 1] == '0':
			time += count1 * (count0 + 1)
	print(time)


t = int(input())
for e in range(t):
	s = input()
	ans = 0
	(a, lens) = ([], len(s))
	for i in range(lens):
		if s[i] == '1':
			a.append(i)
	n = len(a)
	for i in range(n):
		if i == n - 1:
			if a[i] != lens - 1:
				ans += (lens - a[i]) * (i + 1)
		else:
			if a[i + 1] == a[i] + 1:
				continue
			ans += (a[i + 1] - a[i]) * (i + 1)
	print(ans)


for _ in range(int(input())):
	s = input()
	os = 0
	jp = 0
	j = len(s) - 1
	if s[len(s) - 1] == '1':
		while j >= 0:
			if s[j] != '1' or (s[j] == '1' and j == 0):
				i = j - 1
				k = j
				break
			j -= 1
	else:
		i = j - 1
		k = j
	while i >= 0:
		if s[i] == '1':
			jp += k - i + 1
			jp += os
			k -= 1
			if i - 1 >= 0 and s[i - 1] != '1':
				os += 1
		i -= 1
	print(jp)


def calculate(n, N):
	red = []
	b = N.index(1)
	s = 1
	for i in range(b, n):
		if N[i] == 0:
			s += 1
		if N[i] == 1 or i == n - 1:
			if s == 1:
				s = 0
			red.append(s)
			s = 1
	for i in range(len(red) - 2, 0, -1):
		red[i] = red[i] + red[i + 1]
	return sum(red)
T = int(input())
for t in range(T):
	N = [int(i) for i in input()]
	n = len(N)
	if 1 not in N:
		print(0)
	else:
		print(calculate(n, N))


t = int(input())
while t > 0:
	t -= 1
	(count, st) = (0, list(input()))
	m = {}
	tmpC = 0
	for i in range(len(st)):
		if st[i] == '1':
			m[len(m)] = tmpC
			tmpC = 0
		else:
			tmpC += 1
	m[len(m)] = tmpC
	s = 0
	for (key, value) in m.items():
		tmp = key * value
		s += tmp
		if tmp != 0:
			s += key
	print(s)


def getChar(s, ch):
	for i in range(len(s)):
		if s[i] != ch:
			return (s[i:], i)
	return ('', len(s))
T = int(input())
for t in range(T):
	ozs = []
	tot = 0
	count = 0
	moving = False
	s = input().strip()
	s = s[s.find('1'):]
	while len(s) > 0:
		ozs.append([0, 0])
		(s, ozs[count][0]) = getChar(s, '1')
		if len(s) == 0:
			ozs.pop()
			break
		(s, ozs[count][1]) = getChar(s, '0')
		count += 1
	sub_t = 0
	for i in reversed(ozs):
		sub_t += i[1] + 1
		tot += i[0] * sub_t
	print(tot)


T = int(input())
while T > 0:
	a = input()
	s1 = 0
	c1 = 0
	h1 = 0
	l = len(a)
	for i in range(0, l):
		if a[i] == '0':
			h1 = h1 + 1
		else:
			break
	k = h1
	while k < l:
		s = 0
		while a[k] != '0':
			c1 = c1 + 1
			k = k + 1
			if k == l:
				break
		if k == l:
			break
		while a[k] != '1':
			s = s + 1
			k = k + 1
			if k == l:
				break
		s1 = s1 + c1 * (s + 1)
	print(s1)
	T = T - 1


def rowsold(s):
	t = 0
	count0 = 0
	count1 = 0
	for j in range(len(s)):
		if s[j] == '1' or j == len(s) - 1:
			if s[j] == '0':
				count0 = count0 + 1
			if count0 != 0:
				t = t + count1 + count1 * count0
			count1 = count1 + 1
			count0 = 0
		elif s[j] == '0':
			count0 = count0 + 1
	print(t)
for i in range(int(input())):
	rowsold(input())


t = int(input())
for _ in range(t):
	st = input()
	data = []
	temp = 1
	for i in range(1, len(st)):
		if st[i] == st[i - 1]:
			temp += 1
		else:
			data.append((st[i - 1], temp))
			temp = 1
	data.append((st[len(st) - 1], temp))
	ans = 0
	ones = 0
	for d in data:
		if d[0] == '1':
			ones += d[1]
		else:
			ans += ones * (d[1] + 1)
	print(ans)


t = int(input())
while t > 0:
	a = input()
	zerocount = 0
	onecount = 0
	i = 0
	sumi = 0
	while i < len(a):
		if int(a[i]) == 1:
			onecount += 1
		if int(a[i]) == 0:
			j = i
			while j < len(a) and int(a[j]) != 1:
				zerocount += 1
				j += 1
			i = j - 1
		if zerocount:
			sumi = sumi + (zerocount + 1) * onecount
			zerocount = 0
		i += 1
	print(sumi)
	t -= 1


for _ in range(int(input())):
	s = ' ' + input()
	n = len(s) - 1
	ans = 0
	prefix = [0] * (n + 1)
	for i in range(1, n + 1):
		prefix[i] += prefix[i - 1]
		if s[i] == '1':
			prefix[i] += 1
	last = n
	for i in range(n, 0, -1):
		if s[i] == '1':
			ans += last - i
			last -= 1
	for i in range(1, n + 1):
		if s[i] == '0' and i + 1 <= n and (s[i + 1] == '1'):
			ans += prefix[i]
	if s[-1] == '0':
		ans += prefix[-1]
	print(ans)


import re
T = int(input())
for i in range(T):
	num = str(int(input()))
	grouped = [len(m.group(0)) for m in re.finditer('(\\d)\\1*', num)]
	for j in range(1, len(grouped)):
		if j % 2 == 0:
			grouped[j] += grouped[j - 2]
		else:
			grouped[j] += 1
	s = 0
	for k in range(0, len(grouped) - 1, 2):
		s += grouped[k] * grouped[k + 1]
	print(s)


x = int(input())
while x:
	s = input()
	if set(s) == set(['1']):
		print(0)
	else:
		for i in range(len(s) - 1, 0, -1):
			if s[i] == '1':
				s = s[:-1]
			else:
				break
		a = []
		for i in range(len(s)):
			if s[i] == '1':
				a.append(i + 1)
		c = 0
		ans = 0
		if len(a):
			space = 0
			for i in range(len(a) - 1):
				c = c + 1
				space = a[i + 1] - a[i] - 1
				if space:
					ans += space * c + c
			c = c + 1
			space = len(s) - a[len(a) - 1]
			ans += space * c + c
		print(ans)
	x = x - 1


t = int(input())
for i in range(t):
	str = input()
	ls = list(str)
	a = 0
	r = 0
	n = ls.count('1')
	for j in range(len(ls) - 1, -1, -1):
		if ls[j] == '1':
			if a == 0:
				n = n - 1
			else:
				r = r + (a + 1) * n
				n = n - 1
				a = 0
		else:
			a = a + 1
	print(r)


n = int(input())
p = []
for i in range(0, n):
	x = input()
	s1 = 0
	a = [int(j) for j in x]
	from itertools import groupby
	s = [len(list(group)) for (key, group) in groupby(a)]
	if a[0] == 0:
		s = s[1:]
	j = 0
	k = 0
	while j < len(s):
		if j > 0:
			s[j] = s[j] + s[k]
		if j + 1 == len(s):
			break
		s1 = s[j] * (s[j + 1] + 1) + s1
		k = j
		j = j + 2
	p.append(s1)
for i in p:
	print(i)


def rowsold():
	T = int(input())
	for _ in range(T):
		count1 = 0
		sec = 0
		l = [int(d) for d in str(input())]
		try:
			while l[-1] == 1:
				del l[-1]
			while l[0] == 0:
				del l[0]
		except IndexError:
			pass
		for i in range(len(l)):
			if l[i] == 1:
				count1 += 1
			elif l[i - 1] == 1 and l[i] == 0:
				sec = sec + count1 * 2
			elif l[i - 1] == 0 and l[i] == 0:
				sec = sec + count1
		print(sec)
rowsold()


T = int(input())
while T != 0:
	s = input()
	l = len(s)
	no_of_one = 0
	add = 0
	i = 0
	while i < l:
		no_of_zero = 0
		while i < l and s[i] == '1':
			no_of_one += 1
			i += 1
		while i < l and s[i] == '0':
			no_of_zero += 1
			i += 1
		if i < l or s[i - 1] == '0':
			add += no_of_one * (no_of_zero + 1)
	print(add)
	T -= 1


def calc(st):
	cnt = 0
	ones = 0
	enc = False
	zeros = 0
	for i in range(len(st)):
		if st[i] == '1':
			if enc:
				cnt += (zeros + 1) * ones
			enc = False
			ones += 1
			zeros = 0
		elif st[i] == '0':
			if ones:
				if enc:
					zeros += 1
				else:
					zeros = 1
				enc = True
	if zeros:
		cnt += (zeros + 1) * ones
	return cnt
t = int(input())
for _ in range(t):
	a = input()
	print(calc(a))


n = int(input())
for ii in range(n):
	s = list(input())
	if set(s) == set(['1']):
		print('0')
	else:
		while s[-1] == '1':
			s.pop()
		a = []
		for i in range(0, len(s)):
			if s[i] == '1':
				a.append(i + 1)
		c = 0
		ans = 0
		if len(a):
			for i in range(0, len(a) - 1):
				c += 1
				space = a[i + 1] - a[i] - 1
				if space:
					ans += space * c + c
			c += 1
			space = len(s) - a[len(a) - 1]
			ans += space * c + c
		print(ans)


T = int(input())
for t1 in range(T):
	s = input()
	n = len(s)
	sec = 0
	block = 0
	streak = 0
	for q1 in range(n):
		if s[q1] == '1':
			streakover = True
		if block > 0 and streak > 0 and streakover:
			sec += block * (streak + 1)
			streak = 0
		if s[q1] == '1':
			block += 1
			streakover = True
			streak = 0
		elif s[q1] == '0':
			streak += 1
			streakover = False
		if q1 == n - 1 and s[q1] == '0':
			sec += block * (streak + 1)
	print(sec)


repe = int(input())
casos = 0
res = []
while casos < repe:
	cadena = input()
	soldados = 0
	espacios = 0
	tiempo = 0
	tt = 0
	for c in cadena:
		if c == '1':
			if espacios > 0:
				tiempo = soldados + soldados * espacios
				tt += tiempo
				espacios = 0
			soldados += 1
		else:
			espacios += 1
	if espacios > 0:
		tt += soldados + soldados * espacios
	res.append(tt)
	casos += 1
for c in res:
	print(str(c))