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 ith 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.


-----Example-----
Input:
4
47
74
477
4747477

Output:
2
2
3
23

-----Explanation-----

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: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
x = eval(input())
for x in range(0, x):
	ans = 0
	d = input()
	a = 0
	cont = 0
	for i in range(0, len(d)):
		a += len(d) - i
		if d[i] == '7':
			ans += 1 + cont
			cont += 1
		else:
			cont = 0
	ans = a - ans
	print(ans)


for _ in range(int(input())):
	s = input()
	a = s.split('4')
	sum1 = 0
	for k in a:
		sum1 = sum1 + len(k) * (len(k) + 1) / 2
	l = len(s) * (len(s) + 1) / 2
	print(l - sum1)


for _ in range(int(input())):
	s = input().strip()
	ways = 0
	l = len(s)
	index = []
	for i in range(l):
		if s[i] == '4':
			index.append(i)
	if len(index) == 0:
		print(0)
	else:
		ways = 0
		ways += (index[0] + 1 - 0) * (l - index[0])
		for i in range(1, len(index)):
			ways += (index[i] - index[i - 1]) * (l - index[i])
		print(ways)


tcase = int(eval(input()))
i = 0
while tcase:
	tcase -= 1
	a = str(input())
	j = 0
	i = 0
	rem = 0
	length = len(a)
	ans = length * (length + 1) / 2
	while i < length:
		if a[i] == '7':
			rem += i - j + 1
		else:
			j = i + 1
		i += 1
	ans -= rem
	print(ans)


t = int(input().strip())
for i in range(t):
	word = input().strip()
	n = len(word)
	s = n * (n + 1) / 2
	t7 = 0
	for j in range(n):
		if word[j] == '7':
			t7 += 1
		else:
			s -= t7 * (t7 + 1) / 2
			t7 = 0
	s -= t7 * (t7 + 1) / 2
	print(s)