You hava a non-empty string which consists of lowercase English letters and may contain at most one '?'. Let's choose non-empty substring G from S (it can be G = S). A substring of a string is a continuous subsequence of the string. if G contains '?' then '?' can be deleted or replaced by one of lowercase english letters. After that if each letter occurs even number of times in G then G is a good substring. Find number of all good substrings.
Input
The input consists of an integer T, followed by T lines, each containing a non-empty string. The length of the string doesn't exceed 20000.
[b][Technical Specification][/b]
1 <= T <= 100
Output
For each test case, print a single integer which is the number of good substrings of a given string.
Sample Input
3
abc?ca
aabbcc
aaaaa
Sample Output
7
6
6
Hint
Good substrings of "abc?ca": "?", "c?", "?c", "c?c", "bc?c", "c?ca", "abc?ca"
