Medium Math > Counting

You are given a string S consist of character ‘a’ and ‘b’. You have to tell me the number of substring of the given string where there is at most one segment of character b. Suppose the string is “aabbab”. Then some of valid substrings are "a" , "b" , "abb" etc but “bbab” , “bab” etc are not the valid substrings. Input: ------ First line of input contains the number of test case T (1<=T<=100). Then each of the test case contains exactly one line of input string S. Size of the string S will be between 1 and 100000.. Output: ------- For each test cases output a line like **“Case X: Y”** without quotation where X denotes the number of test case and Y denotes the number of sub string of the given test case according to the problem. Sample Input ------------ 1 abba Sample Output ------------- Case 1: 10

Suman Bhadra