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.
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.
For each test case, output a single number, the number of valid substrings.
|M| <= 10^6
M contains only lower case latin latters, that is characters a to z.
Read the editorial here.