beautiful-strings-10

A string is beautiful if it has equal number of a,b,and c in it. 
Example "abc" , "aabbcc" , "dabc" , "" are beautiful.
    Given a string of alphabets containing only lowercas aplhabets (a-z), output the number of non-empty beautiful substring of the given string.

Input 
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a line containing a string a length L.

Output
For each test case, output a single line containing the number of beautiful substring.

Constraints
1 ≤ T ≤ 10
1 ≤ L ≤ 100000

SAMPLE INPUT
2
abacbcba
dbacd

SAMPLE OUTPUT
5
6

Explanation

Test Case 1
The output will be 5 ("abacbc","bac",”acb”, ”acbcba”,"cba")
Test Case 2
The output will be 6 ("d", "dbac", "dbacd", ”bac”, "bacd", "d")

Source: hackerearth | Difficulty: MEDIUM
Tags: Sorting

Ad-hoc


Solutions: