All strings in Chefland are beautiful because they are binary strings (a binary string contains only characters '0' and '1'). The beauty of a binary string $S$ is defined as the number of pairs $(i, j)$ ($1 \le i \le j \le |S|$) such that the substring $S_i, S_{i+1}, \ldots, S_j$ is special.
For a binary string $U$, let's denote the number of occurrences of the characters '1' and '0' in $U$ by $cnt_1$ and $cnt_0$ respectively; then, $U$ is special if $cnt_0 = cnt_1 \cdot cnt_1$.
Today, Chef's friend Araspa is celebrating her birthday. Chef wants to give Araspa the most beautiful binary string he can find. Currently, he is checking out binary strings in a shop, but he needs your help to calculate their beauties. Tell Chef the beauty of each binary string he gives you.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$.

-----Output-----
For each test case, print a single line containing one integer — the beauty of the string $S$.

-----Constraints-----
- $1 \le T \le 10$
- $1 \le |S| \le 10^5$
- each character of $S$ is '0' or '1'

-----Example Input-----
2
010001
10

-----Example Output-----
4
1

-----Explanation-----
Example case 1: The special substrings correspond to $(i, j) = (1, 2), (1, 6), (2, 3), (5, 6)$.

Difficulty: HARD
Tags: Amortized analysis

Range queries

Complete search
Skill types: Amortized analysis

Range queries

Complete search

Starter code:

Solutions:
for i in range(int(input())):
	s = input()
	n = len(s)
	one = [0] * (n + 1)
	for i in range(n):
		if s[i] == '1':
			one[i + 1] = one[i] + 1
		else:
			one[i + 1] = one[i]
	ans = 0
	i = 1
	r = 2
	while r <= n:
		r = i + i ** 2
		j = 0
		while j <= n - r:
			if one[j + r] - one[j] == i:
				ans += 1
				j += 1
			else:
				j += abs(i - (one[j + r] - one[j]))
		i += 1
	print(ans)


for _ in range(int(input())):
	s = input()
	a = []
	a.append(0)
	count = 1
	for i in s:
		if i == '1':
			a.append(a[-1] + 1)
		else:
			a.append(a[-1])
		count += 1
	ans = 0
	i = 1
	r = 2
	while r < count:
		j = 0
		while j < count - r:
			if a[j + r] - a[j] == i:
				ans += 1
				j += 1
			else:
				j += abs(i - (a[j + r] - a[j]))
		i += 1
		r = i + i ** 2
	print(ans)


cnt1_max = 315
arr_size = [None] * cnt1_max
for i in range(1, cnt1_max + 1):
	arr_size[i - 1] = (i * (i + 1), i)
t = int(input())
for _t in range(t):
	s = input()
	n = len(s)
	tot1 = [0] * (n + 1)
	for i in range(1, n + 1):
		if s[i - 1] == '1':
			tot1[i] = tot1[i - 1] + 1
		else:
			tot1[i] = tot1[i - 1]
	beauty = 0
	for (size, cnt) in arr_size:
		i = 0
		limit = n - size
		while i < limit + 1:
			cnt1 = tot1[i + size] - tot1[i]
			if cnt1 == cnt:
				beauty += 1
				i += 1
			else:
				i += abs(cnt1 - cnt)
	print(beauty)


t = int(input())
for k in range(t):
	s = input().strip()
	n = len(s)
	dp = [0]
	for i in s:
		if i == '1':
			dp.append(dp[-1] + 1)
		else:
			dp.append(dp[-1])
	d = 1
	ans = 0
	l = d * d + d
	while l <= n:
		i = 0
		while i <= n - l:
			j = i + l
			cnt1 = dp[j] - dp[i]
			if cnt1 == d:
				ans += 1
				i += 1
			else:
				i += abs(d - cnt1)
		d += 1
		l = d * d + d
	print(ans)


dic = {}
for i in range(1, 316):
	dic[i - 1] = (i * (i + 1), i)
t = int(input())
for _ in range(t):
	arr = list(map(int, input().rstrip()))
	n = len(arr)
	for i in range(1, n):
		arr[i] += arr[i - 1]
	arr.append(0)
	ans = 0
	for (length, cnt1) in dic.values():
		i = 0
		while i + length - 1 < n:
			real_cnt1 = arr[i + length - 1] - arr[i - 1]
			if real_cnt1 == cnt1:
				ans += 1
				i += 1
			else:
				i += abs(cnt1 - real_cnt1)
	print(ans)


t = int(input())

def length(x):
	return x ** 2 + x

def is_valid(count_0, count_1):
	return count_0 == count_1 ** 2
while t:
	t -= 1
	inputs = input()
	counts_1 = []
	n = len(inputs)
	cnt = 0
	for i in range(n):
		if inputs[i] == '1':
			cnt += 1
		counts_1.append(cnt)
	del i
	res = 0
	a = 1
	x = length(a)
	while x <= n:
		if is_valid(x - counts_1[x - 1], counts_1[x - 1]):
			res += 1
		i = x
		while i <= n - 1:
			cnt_1 = counts_1[i] - counts_1[i - x]
			cnt_0 = x - cnt_1
			if is_valid(cnt_0, cnt_1):
				res += 1
				i += 1
			else:
				i += abs(a - cnt_1)
		a += 1
		x = length(a)
	print(res)


try:
	for i in range(int(input())):
		s = input()
		n = len(s)
		count = 0
		ones = [0] * (n + 1)
		for i in range(n):
			if s[i] == '1':
				ones[i + 1] = ones[i] + 1
			else:
				ones[i + 1] = ones[i]
		i = 1
		r = 2
		while r <= n:
			r = i + i * i
			j = 0
			while j <= n - r:
				if ones[j + r] - ones[j] == i:
					count += 1
					j += 1
				else:
					j += abs(i - (ones[j + r] - ones[j]))
			i += 1
		print(count)
except:
	pass


compu = [(x * (x + 1), x) for x in range(1, 316)]
t = int(input())
for i in range(t):
	s = list(map(int, input().strip()))
	count = 0
	arr = [0]
	n = len(s)
	for i in range(1, n + 1):
		arr.append(arr[i - 1] + s[i - 1])
	for (i, a) in compu:
		if i > n:
			break
		s1 = arr[i]
		s0 = i - s1
		if s0 == s1 * s1:
			count += 1
		j = 1
		while j < n - i + 1:
			s1 = arr[i + j] - arr[j]
			s0 = i - s1
			if s0 == s1 * s1:
				count += 1
				j += 1
			else:
				j += abs(a - s1)
	print(count)


from sys import stdin

def sin():
	return stdin.readline()

def ans(s):
	c = 0
	for i in range(len(s)):
		for j in range(i, len(s)):
			d = s[i:j + 1]
			a = d.count('0')
			b = d.count('1')
			if a == b * b:
				c += 1
	return c
test = int(sin())
for _ in range(test):
	s = input()
	x = 1
	ans = 0
	n = len(s)
	te = [0] * (n + 1)
	for i in range(1, n + 1):
		te[i] += te[i - 1] + int(s[i - 1])
	ps = te[0]
	l = x * x + x
	while l <= n:
		i = 0
		while i <= n - l:
			j = i + l
			cnt1 = te[j] - te[i]
			if cnt1 == x:
				ans += 1
				i += 1
			else:
				i += abs(x - cnt1)
		x += 1
		l = x * x + x
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	pref = [0] * len(s)
	if s[0] == '1':
		pref[0] += 1
	for i in range(1, len(s)):
		if s[i] == '1':
			pref[i] += 1
		pref[i] = pref[i] + pref[i - 1]
	k = 1
	cnt = 0
	while k + k * k <= len(s):
		r = k + k * k
		i = r - 1
		while i < len(s):
			if i - r >= 0:
				if pref[i] - pref[i - r] == k:
					cnt += 1
					i += 1
				else:
					i += abs(k - (pref[i] - pref[i - r]))
			elif pref[i] == k:
				cnt += 1
				i += 1
			else:
				i += abs(k - pref[i])
		k += 1
	print(cnt)


def main():
	from collections import defaultdict
	bo = defaultdict(int)
	hash = [0]
	for i in range(1, 350):
		hash.append(hash[-1] + (2 * i - 1))
	from math import sqrt
	for i in range(1, 10 ** 5 + 1):
		bo[i] = int(sqrt(i))
	t = int(input())
	for _ in range(t):
		s = input()
		k = len(s)
		one = [0]
		zer = [0]
		for i in range(len(s)):
			if s[i] == '1':
				one.append(one[-1] + 1)
				zer.append(zer[-1])
			else:
				one.append(one[-1])
				zer.append(zer[-1] + 1)
		ans = 0
		c = 1
		for i in range(1, bo[k] + 1):
			x = 0
			y = c + hash[c] - 1
			while y < len(s):
				no_one = one[y + 1] - one[x]
				zero = zer[y + 1] - zer[x]
				if no_one <= 320:
					if hash[no_one] == zero:
						ans += 1
						x += 1
						y += 1
					else:
						y += (abs(no_one - c) + 1) // 2
						x += (abs(no_one - c) + 1) // 2
				else:
					y += (abs(no_one - c) + 1) // 2
					x += (abs(no_one - c) + 1) // 2
			c += 1
		print(ans)
main()


a = int(input())
for i in range(a):
	S = input()
	N = len(S)
	B = []
	x = 0
	for j in S:
		if j == '1':
			x += 1
		B.append(x)
	ans = 0
	k = 1
	while k ** 2 + k <= N:
		p = k ** 2 + k - 1
		x = B[p]
		j = p
		t = 0
		if p + 1 == N:
			if x == k:
				ans += 1
		else:
			while j <= N - 1:
				if x == k:
					ans += 1
					j += 1
					t += 1
					if j != N:
						x = B[j] - B[t - 1]
				elif j + abs(x - k) <= N - 1:
					j += abs(x - k)
					t += abs(x - k)
					x = B[j] - B[t - 1]
				else:
					break
		k += 1
	print(ans)