A Little Elephant from the Zoo of Lviv likes lucky strings, i.e., the strings that consist only of the lucky digits 4 and 7.

The Little Elephant calls some string T of the length M balanced if there exists at least one integer X (1 ≤ X ≤ M) such that the number of digits 4 in the substring T[1, X - 1] is equal to the number of digits 7 in the substring T[X, M]. For example, the string S = 7477447 is balanced since S[1, 4] = 7477 has 1 digit 4 and S[5, 7] = 447 has 1 digit 7. On the other hand, one can verify that the string S = 7 is not balanced.

The Little Elephant has the string S of the length N. He wants to know the number of such pairs of integers (L; R) that 1 ≤ L ≤ R ≤ N and the substring S[L, R]  is balanced. Help him to find this number.

Notes.

Let S be some lucky string. Then

|S| denotes the length of the string S;

S[i] (1 ≤ i ≤ |S|) denotes the i^{th} character of S (the numeration of characters starts from 1);

S[L, R] (1 ≤ L ≤ R ≤ |S|) denotes the string with the following sequence of characters: S[L], S[L + 1], ..., S[R], and is called a substring of S. For L > R we mean by S[L, R] an empty string.

------ Input ------ 

The first line of the input file contains a single integer T, the number of test cases. Each of the following T lines contains one string, the string S for the corresponding test case. The input file does not contain any whitespaces.

------ Output ------ 

For each test case output a single line containing the answer for this test case.

------ Constraints ------ 

1 ≤ T ≤ 10
1 ≤ |S| ≤ 100000
S consists only of the lucky digits 4 and 7.

----- Sample Input 1 ------ 
4
47
74
477
4747477
----- Sample Output 1 ------ 
2
2
3
23
----- explanation 1 ------ 
In the first test case balance substrings are S[1, 1] = 4 and S[1, 2] = 47.
In the second test case balance substrings are S[2, 2] = 4 and S[1, 2] = 74.
Unfortunately, we can't provide you with the explanations of the third and the fourth test cases. You should figure it out by yourself. Please, don't ask about this in comments.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

String algorithms

Combinatorics

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
import sys
import math

def main(arr):
	n = len(arr)
	ans = n * (n + 1) / 2
	a = 0
	for i in range(len(arr)):
		if arr[i] == '7':
			a += 1
		else:
			ans -= a * (a + 1) / 2
			a = 0
	ans -= a * (a + 1) / 2
	return int(ans)
for _ in range(int(input())):
	arr = list(input())
	print(main(arr))


for _ in range(int(input())):
	s = input()
	(ind, ans) = (-1, 0)
	for i in range(len(s)):
		if s[i] == '4':
			ind = i
		ans += ind + 1
	print(ans)


for i in range(int(input())):
	string = input()
	pos = -1
	res = 0
	for i in range(len(string)):
		if string[i] == '4':
			pos = i
		if pos != -1:
			res += pos + 1
	print(res)


try:
	for i in range(int(input())):
		s = input()
		l = len(s)
		n = -1
		sol = 0
		for i in range(len(s)):
			if s[i] == '4':
				sol += (i - n) * (l - i)
				n = i
		print(sol)
except:
	pass


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


t = int(input())
for i in range(t):
	s = input()
	l = len(s)
	a = -1
	ans = 0
	for j in range(l):
		if s[j] == '4':
			ans += (j - a) * (l - j)
			a = j
	print(ans)