Do you know Professor Saeed? He is the algorithms professor at Damascus University. Yesterday, he gave his students hard homework (he is known for being so evil) - for a given binary string $S$, they should compute the sum of $F(S, L, R)$ over all pairs of integers $(L, R)$ ($1 \le L \le R \le |S|$), where the function $F(S, L, R)$ is defined as follows:
- Create a string $U$: first, set $U = S$, and for each $i$ ($L \le i \le R$), flip the $i$-th character of $U$ (change '1' to '0' or '0' to '1').
- Then, $F(S, L, R)$ is the number of valid pairs $(i, i + 1)$ such that $U_i = U_{i+1}$.
As usual, Professor Saeed will give more points to efficient solutions. Please help the students solve this homework.

-----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 $\sum_{1 \le L \le R \le |S|} F(S, L, R)$.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le |S| \le 3 \cdot 10^6$
- the sum of $|S|$ over all test cases does not exceed $6 \cdot 10^6$

-----Subtasks-----
Subtask #1 (50 points):
- $1 \le |S| \le 300$
- the sum of $|S|$ over all test cases does not exceed $600$
Subtask #2 (50 points): original constraints

-----Example Input-----
1
001

-----Example Output-----
6

-----Explanation-----
Example case 1:
- $L = 1, R = 1$: $U$ is "101", $F = 0$
- $L = 2, R = 2$: $U$ is "011", $F = 1$
- $L = 3, R = 3$: $U$ is "000", $F = 2$
- $L = 1, R = 2$: $U$ is "111", $F = 2$
- $L = 2, R = 3$: $U$ is "010", $F = 0$
- $L = 1, R = 3$: $U$ is "110", $F = 1$

Difficulty: HARD
Tags: Mathematics

Starter code:

Solutions:
def calc(array):
	result = 0
	for i in range(1, len(array)):
		if array[i] == array[i - 1]:
			result += 1
	return result

def answer(p, q):
	result = p * (p - 1) + p * (p - 3) * q // 2
	return result
for test_case in range(int(input())):
	String = input()
	sequence = []
	for i in range(len(String)):
		sequence.append(String[i])
	q = calc(sequence)
	print(answer(len(String), q))


for t in range(int(input())):
	s = input()
	n = len(s)
	total = n * (n + 1) // 2
	count = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			count += total - n
		else:
			count += n
	print(count)


def find2(i):
	ans = 0
	return (i + 1) * (lenS - i - 1) + i * (i + 1) / 2 + (lenS - i - 2) * (lenS - i - 1) / 2
for tests in range(int(input())):
	S = input()
	lenS = len(S)
	ans = 0
	for i in range(lenS - 1):
		if S[i] == S[i + 1]:
			ans += int(find2(i))
		else:
			ans += lenS
	print(ans)


def check(s, n):
	temp = 0
	haha = s[0]
	for i in range(1, n):
		if haha == s[i]:
			temp += 1
		else:
			haha = s[i]
	return temp
for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = 0
	for i in range(n):
		for j in range(i, n):
			temp = s[0:i]
			for t in range(i, j + 1):
				if s[t] == '0':
					temp += '1'
				else:
					temp += '0'
			temp += s[j + 1:]
			ans += check(temp, n)
	print(ans)


from functools import reduce
for _ in range(int(input())):
	s = input()
	l = len(s)
	ans = 0
	for i in range(1, l):
		if s[i] == s[i - 1]:
			ans += int(l * (l - 1) / 2)
		else:
			ans += l
	print(ans)


test = int(input())
for t_count in range(test):
	s = input()
	length = len(s)
	index1 = length * (length - 1) // 2
	index2 = length
	eq_count = 0
	for i in range(1, length):
		if s[i] == s[i - 1]:
			eq_count += 1
	neq_count = length - eq_count - 1
	print(eq_count * index1 + neq_count * index2)


t = int(input(''))
for v in range(t):
	s = input('')
	n = len(s)
	c = 0
	red = 0
	mor = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			c = c + 1
			red = red + n - i - 1
			red = red + i + 1
		else:
			mor = mor + n - i - 1
			mor = mor + i + 1
	ans = n * (n + 1) // 2 * c - red + mor
	print(ans)


try:
	for _ in range(int(input())):
		s = input()
		size = len(s)
		m = size * (size - 1) // 2
		n = size
		answer = 0
		for i in range(size - 1):
			if s[i] == s[i + 1]:
				answer += m
			else:
				answer += n
		print(answer)
except Exception as e:
	print(e)


import math
s = []

def fi(n):
	if n == 0:
		return False
	if s[n] != s[n - 1]:
		return True
	return -1

def ri(n):
	if n == len(s) - 1:
		return False
	if s[n] != s[n + 1]:
		return True
	return -1
for _ in range(int(input())):
	s = input()
	le = len(s)
	count = 0
	for i in range(le - 1):
		if s[i] == s[i + 1]:
			count += 1
	su = le * (le + 1) // 2 * count
	for i in range(1, le + 1):
		su += i * (fi(le - i) + ri(i - 1))
	print(su)


for _ in range(int(input())):
	s = input()
	n = len(s)
	total = 0
	cnt = sum([s[i] == s[i + 1] for i in range(n - 1)])
	subs = n * (n + 1) // 2
	total = subs * cnt
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			total -= n
		else:
			total += n
	print(total)


for _ in range(int(input())):
	s = input()
	n = len(s)
	t = 0
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			t = t + 1
	x = t
	for i in range(n):
		t = x
		if i != 0:
			if s[i] == s[i - 1]:
				t = t - 1
			else:
				t = t + 1
		y = t
		for j in range(i, n):
			t = y
			try:
				if s[j] == s[j + 1]:
					t = t - 1
				else:
					t = t + 1
			except:
				pass
			ans = ans + t
	print(ans)


def func(s):
	n = len(s)
	count = 0
	tot = n * (n + 1) // 2
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			count += tot - n
		else:
			count += n
	return count
t = int(input())
for _ in range(t):
	s = input()
	print(func(s))


for _ in range(int(input())):
	s = input()
	n = len(s)
	total = 0
	previous = s[0]
	for i in range(1, n):
		if s[i] == previous:
			total = total + n * (n - 1) // 2
		else:
			total = total + n
		previous = s[i]
	print(int(total))


t = int(input())
for i in range(t):
	s = input()
	if len(s) == 1:
		print(0)
	else:
		same = 0
		x = 0
		diff = 0
		for j in range(len(s) - 1):
			if s[j] == s[j + 1]:
				x += 1
				same += 1
			else:
				diff += 1
		if same >= 2 and diff >= 2:
			k = (x - 2) * (same * (same - 1)) // 2 + (x + 2) * (diff * (diff - 1)) // 2 + x * diff * same
		elif same < 2 and diff >= 2:
			k = (x + 2) * (diff * (diff - 1)) // 2 + x * diff * same
		elif same >= 2 and diff < 2:
			k = (x - 2) * (same * (same - 1)) // 2 + x * same * diff
		else:
			k = x * same * diff
		k += 2 * (x - 1) * same
		k += 2 * (x + 1) * diff
		k += same
		print(k)


for _ in range(int(input())):
	s = input()
	ans = 0
	n = len(s)
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans += n * (n - 1) // 2
		else:
			ans += n
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	s = list(s)
	n = len(s)
	cnt = 0
	for i in range(n):
		for j in range(i, n):
			temp = s[:]
			for k in range(i, j + 1):
				if temp[k] == '1':
					temp[k] = '0'
				else:
					temp[k] = '1'
			for k in range(n - 1):
				if temp[k] == temp[k + 1]:
					cnt += 1
	print(cnt)


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	k = n * (n + 1) // 2
	x = n * (n - 1) // 2
	sum = 0
	for i in range(0, n - 1):
		if s[i] == s[i + 1]:
			sum = sum + x
		else:
			sum = sum + k - x
	print(sum)
	t = t - 1


from collections import defaultdict
mod = 10 ** 9 + 7
T = 1
T = int(input())
for _ in range(T):
	s = input()
	ans = 0
	n = len(s)
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			ans += n * (n + 1) // 2
			ans -= n
		else:
			ans += n
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	k = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			k += 1
	ans = k * (n * (n + 1) // 2)
	for i in range(n):
		x = n - i
		if i == 0:
			pass
		elif s[i] == s[i - 1]:
			ans -= x
		else:
			ans += x
		x = i + 1
		if i == n - 1:
			pass
		elif s[i + 1] == s[i]:
			ans -= x
		else:
			ans += x
	print(ans)


def q():
	meanAllPop = []
	meanResPop = []
	for t in range(len(allVirusPop[0])):
		summAll = 0
		for n in range(len(allVirusPop)):
			summAll += float(allVirusPop[n][t])
		summRes = 0
		for n in range(len(resistVirusPop)):
			summRes += float(resistVirusPop[n][t])
		meanAllPop.append(summAll / float(numTrials))
		meanResPop.append(summRes / float(numTrials))

def left(s, n):
	if n == 0:
		return 0
	if s[n] != s[n - 1]:
		return 1
	return -1

def right(s, n):
	if n == len(s) - 1:
		return 0
	if s[n] != s[n + 1]:
		return 1
	return -1

def main():
	for _ in range(int(input())):
		s = list(input())
		count = 0
		for i in range(len(s) - 1):
			if s[i] == s[i + 1]:
				count += 1
		ans = len(s) * (len(s) + 1) // 2
		ans *= count
		for i in range(1, len(s) + 1):
			ans += i * left(s, len(s) - i)
			ans += i * right(s, i - 1)
		print(ans)
main()


for _ in range(int(input())):
	s = input()
	N = len(s)
	answer = 0
	h = N * (N - 1) // 2
	for i in range(N - 1):
		if s[i] == s[i + 1]:
			answer = answer + h
		else:
			answer = answer + N
	print(answer)


for a0 in range(int(input())):
	s = input()
	ct = 0
	n = len(s)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ct += n * (n - 1) // 2
		else:
			ct += n
	print(ct)


def reverse(a):
	if a == 0:
		return 1
	else:
		return 0
t = int(input())
for x0 in range(t):
	strs = input()
	i = 1
	array = []
	while i < len(strs):
		if strs[i] != strs[i - 1]:
			array.append(0)
		else:
			array.append(1)
		i += 1
	n = len(strs)
	flips = n * (n + 1) // 2
	sums = 0
	i = 0
	while i < len(array):
		change = n
		sums += change * reverse(array[i])
		sums += (flips - change) * array[i]
		i += 1
	print(sums)


t = int(input())
for tt in range(t):
	s = input()
	n = len(s)
	c = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			c += 1
	p1 = int(n * (n + 1) / 2 - n)
	p2 = int(n * (n - c - 1))
	print(p1 * c + p2)


t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	ans = 0
	for i in range(l - 1):
		if s[i] == s[i + 1]:
			ans += int(l * (l - 1) / 2)
		else:
			ans += l
	print(ans)


def snek1(a):
	r = 0
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			r += 1
	return r

def snek2(p, q):
	r = p * (p - 1) + p * (p - 3) * q // 2
	return r
t = int(input())
for i in range(t):
	n = input()
	s = []
	for j in range(len(n)):
		s.append(n[j])
	q = snek1(s)
	print(snek2(len(n), q))


def funct(n):
	n = n - 1
	p = n ** 2
	p = p * (n + 1)
	p = p // 2
	return p
for _ in range(int(input())):
	s = input()
	n = len(s)
	p = funct(n)
	o = s.count('1')
	x = n - 3
	if n == 1:
		q = 0
	elif n == 2:
		q = 1
	else:
		q = (x + 1) * (x + 2) // 2 - 1
	count = 0
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			count = count + 1
	print(p - count * q)


t = int(input())
for _ in range(t):
	string = str(input())
	n = len(string)
	m = n * (n - 1) / 2
	ans = 0
	for i in range(n - 1):
		if string[i] == string[i + 1]:
			ans += int(m)
		else:
			ans += n
	print(ans)


a = int(input())
answer = []
for i in range(a):
	s = input()
	l = len(s)
	ans = 0
	for i in range(l - 1):
		if s[i] == s[i + 1]:
			ans = ans + (l - 1) * l / 2
		elif s[i] != s[i + 1]:
			ans = ans + l
	answer.append(ans)
for i in range(a):
	print(int(answer[i]))


for test in range(int(input())):
	s = input()
	n = len(s)
	a = n * (n - 1) // 2
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans += a
		else:
			ans += n
	print(ans)


def evil(s):
	n = len(s)
	ans = 0
	count1 = 0
	count2 = 0
	if n > 1:
		for i in range(0, n - 1):
			if s[i] == s[i + 1]:
				count1 += 1
			else:
				count2 += 1
		ans = count1 * (n * (n - 1) // 2) + count2 * n
	return ans
t = int(input())
for i in range(0, t):
	s = input()
	print(evil(s))


t = int(input())
while t:
	t -= 1
	a = input().rstrip()
	n = len(a)
	s = 0
	for i in range(n - 1):
		if a[i] == a[1 + i]:
			s += n * (n - 1) // 2
		else:
			s += n
	print(s)


for i in range(int(input())):
	ans = 0
	str1 = input()
	n = len(str1)
	for j in range(n - 1):
		if str1[j] == str1[j + 1]:
			ans += n * (n - 1) // 2
		else:
			ans += n
	print(ans)


def formula(n):
	if n < 0:
		return 0
	return (n * n + n) // 2

def solve(s):
	n = len(s)
	if n <= 1:
		return 0
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans += formula(i) + formula(n - i - 2) + (i + 1) * (n - i - 1)
		else:
			ans += n
	return ans
t = int(input())
for _ in range(t):
	s = input()
	print(solve(s))


s = []

def l(n):
	if n == 0:
		return False
	if s[n] != s[n - 1]:
		return True
	return -1

def r(n):
	if n == len(s) - 1:
		return False
	if s[n] != s[n + 1]:
		return True
	return -1
for _ in range(int(input())):
	s = input()
	le = len(s)
	count = 0
	for i in range(le - 1):
		if s[i] == s[i + 1]:
			count += 1
	su = le * (le + 1) // 2 * count
	for i in range(1, le + 1):
		su += i * (l(le - i) + r(i - 1))
	print(su)


for _ in range(int(input())):
	s = input()
	n = len(s)
	count = 0
	s = list(map(int, list(s)))
	for i in range(n - 1):
		if s[i] != s[i + 1]:
			count += 1
	x = 2 * count - n + 1
	print((n - 1 - count) * n * (n + 1) // 2 + x * n)


for t in range(int(input())):
	s = input()
	n = len(s)
	inversion = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			inversion += 1
	ans = n * (n + 1) // 2 * inversion
	for i in range(n):
		left = n - i
		right = i + 1
		if i != 0:
			if s[i - 1] == s[i]:
				ans -= left
			else:
				ans += left
		if i != n - 1:
			if s[i + 1] == s[i]:
				ans -= right
			else:
				ans += right
	print(ans)


for t in range(int(input())):
	s = input()
	lst = []
	(n, cou) = (len(s), 0)
	a = s[0]
	for i in range(1, n):
		if s[i] == a:
			lst.append(1)
			cou += 1
		else:
			lst.append(-1)
		a = s[i]
	print(n * (n + 1) * cou // 2 - n * sum(lst))


for _ in range(int(input())):
	s = input()
	n = len(s)
	same = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			same += 1
	diff = n - 1 - same
	k = n * (n + 1) // 2
	res = k * same + n * (diff - same)
	print(res)


t = int(input())
for ii in range(t):
	arr = list(input())
	n = len(arr)
	a = n * (n - 1) // 2
	b = n
	eq = 0
	neq = 0
	for i in range(1, n):
		if arr[i] == arr[i - 1]:
			eq += 1
		else:
			neq += 1
	print(eq * a + neq * b)


for test in range(int(input())):
	s = str(input())
	size = len(s)
	same = size * (size - 1) // 2
	diff = size
	out = 0
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			out += same
		else:
			out += diff
	print(out)


from sys import stdin
for __ in range(int(stdin.readline().split()[0])):
	string = stdin.readline().split()[0]
	n = len(string)
	ans = 0
	for i in range(n - 1):
		if string[i] == string[i + 1]:
			ans += n - 2
			ans += i * (i - 1) // 2
			ans += (n - i - 2) * (n - i - 3) // 2
			ans += (i + 1) * (n - i - 1)
		else:
			ans += 2
			ans += i
			ans += n - i - 2
	print(int(ans))


t = int(input())
for i in range(t):
	count = 0
	string = input()
	length = len(string)
	for i in range(0, length - 1):
		x = i
		y = length - x - 2
		if string[i] == string[i + 1]:
			count += (x + 1) * x // 2 + (y + 1) * y // 2 + (x + 1) * (y + 1)
		else:
			count += x + y + 2
	print(int(count))


t = int(input())
for _ in range(t):
	s = input()
	k = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			k += 1
	ans = 0
	for i in range(len(s)):
		for j in range(i, len(s)):
			ans += k
			if i == 0:
				pass
			elif s[i - 1] == s[i]:
				ans -= 1
			else:
				ans += 1
			if j == len(s) - 1:
				pass
			elif s[j + 1] == s[j]:
				ans -= 1
			else:
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	hak = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			hak += 1
	red = hak * n * (n + 1)
	red = red // 2
	clu = n * n
	qwe = 2 * hak * n
	print(red + clu - qwe - n)


def testcase():
	s = input()
	answer = 0
	n = len(s)
	for i in range(0, n - 1):
		if s[i] == s[i + 1]:
			answer += n * (n + 1) // 2 - n
		else:
			answer += n
	print(answer)
t = int(input())
for test in range(t):
	testcase()


def solve():
	t = int(input())
	for i in range(0, t):
		s = input()
		ans = 0
		sums = 0
		for k in range(0, len(s) - 1):
			if s[k] == s[k + 1]:
				sums += 1
		ans = len(s) * (len(s) + 1) / 2 * sums
		for l in range(0, len(s)):
			for r in range(l, len(s)):
				if l > 0:
					if s[l - 1] == s[l]:
						ans -= 1
					else:
						ans += 1
				if r < len(s) - 1:
					if s[r] == s[r + 1]:
						ans -= 1
					else:
						ans += 1
		print(int(ans))
solve()


for _ in range(int(input())):
	s = input()
	m = ''
	for i in range(len(s) - 1):
		if s[i] == s[i + 1]:
			m += '1'
		else:
			m += '0'
	cnt = m.count('1')
	n = len(s)
	ans = 0
	for i in range(n - 1):
		temp = cnt
		if m[i] == '1':
			temp -= 1
		else:
			temp += 1
		ans += temp
	flag = (n - 1) * (n - 2)
	flag = flag // 2
	flag = (flag - 1) * cnt
	print(ans * n - flag)


for i in range(int(input())):
	s = input()
	count = 0
	l = len(s)
	for j in range(l - 1):
		if s[j] == s[j + 1]:
			count += 1
	count *= l * (l + 1) // 2
	if l == 1:
		print(0)
	else:
		if s[0] == s[1]:
			count -= 1
		else:
			count += 1
		for j in range(1, l):
			if j != l - 1:
				if s[j] == s[j + 1]:
					count -= j + 1
				else:
					count += j + 1
			if s[j] == s[j - 1]:
				count -= l - j
			else:
				count += l - j
		print(count)


t = int(input())
while t > 0:
	s = input()
	length = len(s)
	ans = 0
	for l in range(length):
		for r in range(l, length):
			temp = s
			x = temp[:l]
			for i in range(l, r + 1):
				if temp[i] == '0':
					x += '1'
				else:
					x += '0'
			x += temp[r + 1:]
			for k in range(len(x) - 1):
				if x[k] == x[k + 1]:
					ans += 1
	print(ans)
	t -= 1