Counting Strings
Algorithms
Easy
28.0% success
9,419 attempts
5s time
256MB memory
1024KB max code
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.
Examples
Input
4 abcd azazaz abbzbba flkjdh
Output
4 21 22 0
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Loading Editor...