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