Problem Description

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.

[Technical Specification]
1 <= T <= 100

Output

For each test case, print a single integer which is the number of good substrings of a given string.

3
abc?ca
aabbcc
aaaaa

7
6
6

Hint

Good substrings of "abc?ca": "?", "c?", "?c", "c?c", "bc?c", "c?ca", "abc?ca"