The notorious hacker group "Sed" managed to obtain a string $S$ from their secret sources. The string contains only lowercase English letters along with the character '?'.
A substring of $S$ is a contiguous subsequence of that string. For example, the string "chef" is a substring of the string "codechef", but the string "codeh" is not a substring of "codechef".
A substring of $S$ is good if it is possible to choose a lowercase English letter $C$ such that the following process succeeds:
- Create a string $R$, which is a copy of the substring, but with each '?' replaced by the letter $c$. Note that all occurrences of '?' must be replaced by the same letter.
- For each lowercase English letter:
- Compute the number of times it occurs in $S$ and the number of times it occurs in $R$; let's denote them by $A$ and $B$ respectively. The '?' characters in the original string $S$ are ignored when computing $A$.
- Check the parity of $A$ and $B$. If they do not have the same parity, i.e. one of them is even while the other is odd, then this process fails.
- If the parities of the number of occurrences in $S$ and $R$ are the same for each letter, the process succeeds.
For different substrings, we may choose different values of $C$.
Help Sed find the number of good substrings in the string $S$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains a single string $S$.

-----Output-----
For each test case, print a single line containing one integer ― the number of good substrings.

-----Constraints-----
- $1 \le T \le 10^5$
- $1 \le S \le 10^5$
- $S$ contains only lowercase English letters ('a' through 'z') and '?'
- the sum of $|S|$ over all test cases does not exceed $10^5$

-----Example Input-----
5
aa?
a???
????
asfhaslskfak
af??avvnfed?fav?faf????

-----Example Output-----
2
6
4
2
27

-----Explanation-----
Example case 1: All letters occur an even number of times in $S$. The six substrings of $S$ are "a", "a", "?", "aa", "a?" and "aa?" (note that "a" is counted twice). Which of them are good?
- "a" is not good as 'a' occurs an odd number of times in this substring and there are no '?' to replace.
- "?" is also not good as replacing '?' by any letter causes this letter to occur in $R$ an odd number of times.
- "aa" is a good substring because each letter occurs in it an even number of times and there are no '?' to replace.
- "a?" is also a good substring. We can replace '?' with 'a'. Then, $R$ is "aa" and each letter occurs in this string an even number of times. Note that replacing '?' e.g. with 'b' would not work ($R$ would be "ab", where both 'a' and 'b' occur an odd number of times), but we may choose the replacement letter $C$ appropriately.
- "aa?" is not a good substring. For any replacement letter $C$, we find that $C$ occurs an odd number of times in $R$.
Example case 2: We especially note that "a???" is not a good substring. Since all '?' have to be replaced by the same character, we can only get strings of the form "aaaa", "abbb", "accc", etc., but none of them match the criteria for a good substring.
Example case 3: Any substring with even length is good.

Difficulty: interview

Starter code:

Solutions:
def convertToParitys(s):
    """
    This converts the string s to an int, which is a bitMap of the parity of each letter
    odd ? = first bit set
    odd a = second bit set
    odd b = third bit set 
    etc
    """
    keys = '?abcdefghijklmnopqrstuvwxyz'
    paritys = {c:0 for c in keys}
    for c in s:
        paritys[c] += 1
    for c, v in paritys.items():
        paritys[c] = v%2
    
    out = 0
    bitValue = 1
    for c in keys:
        if paritys[c]:
            out += bitValue
        bitValue *= 2
    return out

def getSolutionBitMaps(s):
    """
    these are the 27 valid bitmaps that a substring can have
    even ? and the parities the same
    26 cases of odd ? and one bit different in the parity compared to s
    """
    out = []
    sP = convertToParitys(s)
    if sP%2:
        sP -= 1 # to remove the '?' parity
    #even case - 
    out.append(sP)
    #odd cases - need to xor sP with 1 + 2**n n = 1 to 26 inc to flip ? bit and each of the others
    for n in range(1,27):
        out.append(sP^(1+2**n))
    return out

def getLeadingSubStringBitMapCounts(s):
    """
    This calculates the bit map of each of the len(s) substrings starting with the first character and stores as a dictionary.
    Getting TLE calculating each individually, so calculating with a single pass
    """
    out = {}
    bM = 0
    keys = '?abcdefghijklmnopqrstuvwxyz'
    paritys = {c:0 for c in keys}
    values = {c:2**i for i,c in enumerate(keys)}
    out[bM] = out.setdefault(bM, 0) + 1  #add the null substring
    bMis = []
    i = 0
    bMis = [0]
    for c in s:
        i += 1
        if paritys[c]:
            paritys[c] = 0
            bM -= values[c]
        else:
            paritys[c] = 1
            bM += values[c]
        out[bM] = out.setdefault(bM, 0) + 1
        bMis.append(bM)
    return out,bMis

def solve(s):
    out = 0
    bMjCounts,bMis = getLeadingSubStringBitMapCounts(s)
    #print('bMjCounts')
    #print(bMjCounts)
    solutions = getSolutionBitMaps(s)
    #print('solutions')
    #print(solutions)    
    for bMi in bMis:
        for bMs in solutions:
            if bMs^bMi in bMjCounts:
                out += bMjCounts[bMs^bMi]
                #print(i,bMi,bMs,bMs^bMi,bMjCounts[bMs^bMi])
    if 0 in solutions:
        out -= len(s) #remove all null substrings
    out //= 2 # since j may be less that i each substring is counted twice
    return out
                
T = int(input())
for tc in range(T):
    s = input()
    print(solve(s))
    

"""
Code Chef :: December 2020 Cookoff :: Sed Passwords 
Problem Code: SEDPASS
https://www.codechef.com/COOK125A/problems/SEDPASS
"""
import sys


def solve(S):
    """Solve puzzle."""
    N = len(S)
    parity_S = 0
    qs_add = (1 << 26)
    ord_a = ord('a')
    for i, c in enumerate(S):
        if c != '?':
            parity_S ^= (1 << (ord(c) - ord_a))

    # The 27 good bitsets.
    # The first is even parity ?s (26th bit = 0) and parity_S
    good_Rs = [parity_S]
    for c in range(26):
        # The rest are odd parity ?s (26th bit) and parity_S with one
        # character, c, with the opposite parity.
        good_Rs.append((parity_S ^ (1 << c)) | qs_add)

    # A substring S[i:j] has a parity of S[:j] ^ S[:i].
    # a ^ b = c implies a ^ c = b.
    # If S[:j] ^ a good_Rs = some S[:i] then S[i:j] is a good substring.
    # So if we keep track of the S[:i] that we have already seen and 
    # at each j check each good_Rs to see if it matches previous S[:j]s
    # that we have cached.  Note: a subtring parity may occur more than once.
    prefix_parities = dict()
    prefix_parities[0] = 1  # Be sure to add an empty S[:i].

    parity_R = 0
    soln = 0
    for j, c in enumerate(S):
        if c == "?":
            parity_R ^= qs_add
        else:
            parity_R ^= (1 << (ord(c) - ord_a))

        for good_R in good_Rs:
            soln += prefix_parities.get(good_R ^ parity_R, 0)
        if parity_R in prefix_parities:
            prefix_parities[parity_R] += 1
        else:
            prefix_parities[parity_R] = 1

    return soln


def main():
    """Main program."""
    test_cases = int(sys.stdin.readline())
    for _ in range(test_cases):
        S = sys.stdin.readline().strip()
        print(solve(S))


def __starting_point():
    main()

__starting_point()

'''Author- Akshit Monga'''
# Complexity- (26*|S|)
from sys import stdin,stdout
input = stdin.readline
def val(i):
    if i=='?':
        return 26
    return ord(i)-97
t = int(input())
for _ in range(t):
    s=input()[:-1]
    ans=0
    mask=0
    for i in s:
        if i=='?':
            continue
        mask^=(1<<val(i))
    hash={0:1}
    pre=0
    for i in s:
        pre^=(1<<val(i))
        ans+=hash.get(pre^mask,0)
        x=mask^(1<<26)
        for j in range(26):
            ans+=hash.get(pre^(1<<j)^x,0)
        hash[pre]=hash.get(pre,0)+1
    stdout.write(str(ans)+'\n')

'''Author- Akshit Monga'''
# Complexity- (26*26*|S|)
from sys import stdin,stdout
input = stdin.readline
t = int(input())
for _ in range(t):
    s=input()[:-1]
    n=len(s)
    mask=[0 for i in range(26)]
    for i in s:
        if i=='?':
            continue
        mask[ord(i)-97]^=1
    good=[mask+[0]]
    for i in range(26):
        temp=mask.copy()
        temp[i]^=1
        good.append(temp+[1])
    pre_masks={'0'*27:1}
    temp=[0 for i in range(27)]
    ans=0
    for i in range(n):
        if s[i]=='?':
            temp[26]^=1
        else:
            temp[ord(s[i])-97]^=1
        good1=mask+[0]
        xor = ''
        for j in range(27):
            xor += str(temp[j] ^ good1[j])
        if xor in pre_masks:
            ans += pre_masks[xor]
        good2=mask+[1]
        xor1 = ''
        for j in range(27):
            xor1 += str(temp[j] ^ good2[j])
        for j in range(26):
            xor2=xor1[:j]+str(int(xor1[j])^1)+xor1[j+1:]
            if xor2 in pre_masks:
                ans += pre_masks[xor2]
        pre=''.join([str(e) for e in temp])
        if pre in pre_masks:
            pre_masks[pre]+=1
        else:
            pre_masks[pre]=1
    stdout.write(str(ans)+'\n')

'''Author- Akshit Monga'''
# Complexity- (26*26*|S|)
from sys import stdin,stdout
input = stdin.readline
t = int(input())
for _ in range(t):
    s=input()[:-1]
    n=len(s)
    mask=[0 for i in range(26)]
    for i in s:
        if i=='?':
            continue
        mask[ord(i)-97]^=1
    good=[mask+[0]]
    for i in range(26):
        temp=mask.copy()
        temp[i]^=1
        good.append(temp+[1])
    pre_masks={'0'*27:1}
    temp=[0 for i in range(27)]
    ans=0
    for i in range(n):
        if s[i]=='?':
            temp[26]^=1
        else:
            temp[ord(s[i])-97]^=1
        good1=mask+[0]
        xor = ''
        for j in range(27):
            xor += str(temp[j] ^ good1[j])
        if xor in pre_masks:
            ans += pre_masks[xor]
        good2=mask+[1]
        xor1 = ''
        for j in range(27):
            xor1 += str(temp[j] ^ good2[j])
        for j in range(26):
            xor2=xor1[:j]+str(int(xor1[j])^1)+xor1[j+1:]
            if xor2 in pre_masks:
                ans += pre_masks[xor2]
        pre=''.join([str(e) for e in temp])
        if pre in pre_masks:
            pre_masks[pre]+=1
        else:
            pre_masks[pre]=1
    stdout.write(str(ans)+'\n')

# from sys import stdin, stdout
# from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
# from collections import defaultdict as dd, deque
# from heapq import merge, heapify, heappop, heappush, nsmallest
# from bisect import bisect_left as bl, bisect_right as br, bisect
# mod = pow(10, 9) + 7
# mod2 = 998244353
# def inp(): return stdin.readline().strip()
# def out(var, end="\n"): stdout.write(str(var)+"\n")
# def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
# def lmp(): return list(mp())
# def mp(): return map(int, inp().split())
# def smp(): return map(str, inp().split())
# def l1d(n, val=0): return [val for i in range(n)]
# def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
# def remadd(x, y): return 1 if x%y else 0
# def ceil(a,b): return (a+b-1)//b

# def isprime(x):
#     if x<=1: return False
#     if x in (2, 3): return True
#     if x%2 == 0: return False
#     for i in range(3, int(sqrt(x))+1, 2):
#         if x%i == 0: return False
#     return True
    
# def bitmsk(s):
#     md = {}
#     S = "abcdefghijklmnopqrstuvwxyz"
#     for i in S:
#         md[i]=0
#     for i in s:
#         if i in md: md[i]+=1
#     b = ""
#     for i in S:
#         b+='1' if md[i]%2 else '0'
#     return b

# def xor(a, b):
#     c = ""
#     for i in range(27):
#         if (a[i]=='0' and b[i]=='0') or (a[i]=='1' and b[i]=='1'): c += '0'
#         else: c += '1'
#     return c

# for _ in range(int(inp())):
#     s = inp()
#     l = len(s)
#     b = bitmsk(s)
#     b += '0'
#     good = []
#     good.append(b)
#     b = b[:-1]
#     for i in range(26):
#         x = '1' if b[i]=='0' else '0'
#         good.append(b[:i]+x+b[i+1:]+'1')
#     pre = ['0'*27]
#     cq = 0
#     mdd = {}
#     for i in range(l):
#         if s[i]=='?': cq+=1
#         k = '1' if cq%2 else '0'
#         kk = bitmsk(s[:i+1])+k
#         pre.append(kk)
#         if kk in mdd: mdd[kk].append((i+1))
#         else: mdd[kk]=[(i+1)]
#     # print(pre)
#     ans = 0
#     for i in range(l):
#         # for j in range(i+1, l+1):
#         #     if xor(pre[i], pre[j]) in good:
#         #         ans += 1
#         for j in good:
#             xx = xor(pre[i], j)
#             if xx in mdd:
#                 ans += len(mdd[xx])-br(mdd[xx], i)
#     out(ans)

# cook your dish here
from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353
def inp(): return stdin.readline().strip()
def out(var, end="\n"): stdout.write(str(var)+"\n")
def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
def lmp(): return list(mp())
def mp(): return map(int, inp().split())
def smp(): return map(str, inp().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
def remadd(x, y): return 1 if x%y else 0
def ceil(a,b): return (a+b-1)//b

def isprime(x):
    if x<=1: return False
    if x in (2, 3): return True
    if x%2 == 0: return False
    for i in range(3, int(sqrt(x))+1, 2):
        if x%i == 0: return False
    return True
    
def xor(a, b):
    c = ""
    for i in range(27):
        if (a[i]=='0' and b[i]=='0') or (a[i]=='1' and b[i]=='1'): c += '0'
        else: c += '1'
    return c

for _ in range(int(inp())):
    s = inp()
    l = len(s)
    md = {}
    S = "abcdefghijklmnopqrstuvwxyz"
    for i in S:
        md[i]=0
        
    cq = 0
    mdd = {}
    pre = ['0'*27]
    for i in range(l):
        if s[i] in md: md[s[i]]+=1
        b = ""
        for j in S:
            b+='1' if md[j]%2 else '0'
        if s[i]=='?': cq+=1
        k = '1' if cq%2 else '0'
        kk = b+k
        pre.append(kk)
        if kk in mdd: mdd[kk].append((i+1))
        else: mdd[kk]=[(i+1)]
        
    b = pre[-1]
    good = []
    good.append(b[:-1]+'0')

    b = b[:-1]
    for i in range(26):
        x = '1' if b[i]=='0' else '0'
        good.append(b[:i]+x+b[i+1:]+'1')
    alpha = {}
    S = "abcdefghijklmnopqrstuvwxyz?"
    for i in range(27):
        alpha[S[i]] = i
    
    ans = 0
    for j in good:
        prev = j
        for i in range(l+1):
            if i != 0:
                x = alpha[s[i-1]]
                kk = '0' if prev[x] == '1' else '1'
                prev = prev[:x]+kk+prev[x+1:]
            if prev in mdd:
                ans += len(mdd[prev])-br(mdd[prev], i)
    out(ans)

# cook your dish here
def letterNo(c):
    if i == '?':
        return 26
    return ord(c) - 97
for _ in range(int(input())):
    s = input().strip()
    mask = 0
    for i in s:
        if i != '?':
            mask ^= (1 << letterNo(i))
    d = {}
    x = 0
    d[0] = 1
    ans = 0
    for i in s:
        x ^= (1 << letterNo(i))
        ans += d.get(x^mask, 0)
        for j in range(26):
            ans += d.get(x^(1 << 26)^(1 << j)^mask, 0)
        d[x] = d.get(x, 0) + 1
    print(ans)


def to_bit(c):
    if c == "?":
        bit = 26
    else:
        bit = (ord(c)-ord('a'))
    return bit
    
T = int(input())
for _ in range(T):
    s = input()
    
    mask = 0
    for c in s:
        if c != "?":
            mask ^= 1 << to_bit(c)
    
    good_prefixes = []
    good_prefixes.append(mask & ((1 << to_bit("?")) - 1))
    for i in range(26):
        good_prefixes.append((mask ^ (1<<i)) | (1 << to_bit("?")))
    
    prefixes = { 0: 1}
  
    res = 0
    current = 0
    for c in s:
        current ^= 1 << to_bit(c)
        for prefix in good_prefixes:
            res += prefixes.get(prefix ^ current, 0)
        prefixes[current] = prefixes.get(current, 0) + 1
    
    print(res)