counting-strings

Alice got a message M. It is in an alien language. A string in an alien language is said to be valid if it contains the letter a or z.  Alice decided to count the number of valid substrings  of the message M. Help him to do this. Two substrings are different if it occurs at different positions in the message.  

Input
First line of the input contains the number of test cases T. It is followed by T lines. Each line has a single string M.  

Output
For each test case, output a single number, the number of valid substrings.   

Constraints
|M| ≤ 10^6 
M contains only lower case latin latters, that is characters a to z.

Read the editorial here.

SAMPLE INPUT
4
abcd
azazaz
abbzbba
flkjdh

SAMPLE OUTPUT
4
21
22
0

Difficulty: EASY

Starter code:

Solutions:
def solution(string):
	n = len(string)
	comb = n*(n+1)/2
	if ('a' not in string) and ('z' not in string):
		return 0
	else:
		substrings = string.replace('z', 'a').split('a')
		for i in substrings:
			comb -= (len(i) * (len(i)+1)) / 2
		return comb

t = int( input() )
for i in range( t ):
	print(solution(input()))



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

n = int(input())
i = 0
ctr = 0
ans = 0
while i < n:
	tc = input()
	j = 0
	while j < len(tc):
		#print j, " - "
		if tc[j] == 'a' or tc[j] == 'z':
			#ctr = j + 1
			#print "ctr", ctr
			ans += j+1
			ctr = j+1
		else:
			ans += ctr
		#ans = ans + ctr
		#print "ans", ans
		j += 1
	i += 1
	print(ans)
	ans = 0
	ctr = 0


#! /usr/bin/python

t = int(input())
for x in range(t):
	m = input()
	l = len(m)
	c = 0
	r = 0
	for i in range(l):
		if (m[i] == 'a' or m[i] == 'z'):
			r += (c * (c + 1)) / 2
			c = 0
		else:
			c += 1
		
	r += (c * (c + 1))/2
	total = (l * (l + 1))/2
	ans = total - r
	print(ans)


t=eval(input())
for i in range(t):
	s=input()
	s = s.replace('z', 'a')
	"""
	s = s.replace('z', 'a')
	r = len(s)
	print r
	r = r * (r+1) / 2
	tmp = s.split('a')
	print tmp
	tmp = [len(i)*(len(i)+1)/2 for i in tmp]
	print tmp
	print r - sum(tmp)
	"""
	l=len(s)
	ts = l*(l+1)/2
	arr = []
	a=0
	for j in range(l):
		if(s[j] != 'a'):
			a=a+1
			arr.append(a)
		else:
			a=0
			arr.append(a)
	su=sum(arr)
	print(ts-su)


t=int(input())
while t>0:
	st=input()
	l=0
	res=0
	for i in range(len(st)):
		if st[i]=='a' or st[i]=='z':
			l=i+1
		res=res+l
	print(res)
	t=t-1
			


for i in range(eval(input())):
	s=input()
	a=0
	b=0
	for i in range(len(s)):
		if(s[i] =='a' or s[i] =='z'):
			a=i+1
		b+=a
	print(b)


t=eval(input())
while(t>0):
	line=input()
	count=0
	sum=0
	l=len(line)
	l=l-1
	for num in range(0,l+1):
		if line[num]=='a' or line[num]=='z':
			temp=l-num
			#sum=sum+1
			sum=sum+temp+1
			sum=sum+(count*(temp+1))
			count=0
		else:
			count=count+1
	print(sum)
			
			
			
	t=t-1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

for i in range(eval(input())):
	s=input()
	a=0
	b=0
	for i in range(len(s)):
		if(s[i] =='a' or s[i] =='z'):
			a=i+1
		b+=a
	print(b)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input())

while t:
	t-=1
	s = input().strip()
	
	count = 0
	prev = 0
	curr = 0
	l = len(s)
	s = s.replace("a", "z")
	if "z" in s:
		for i, v in enumerate(s):
			if v == "z":
				count += l - i
				prev += curr
				count += prev
				
				curr = 0
			else:
				count += prev
				curr += 1
				
	
	print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
for t in range(int(input())):
	m = input()
	pi,i = -1,0
	l = len(m)
	ret = 0
	while i<l:
		if m[i]=='a' or m[i]=='z':
			ret += (l - i) * (i-pi)
			pi = i
		i+=1
	print(ret)