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
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")