Counting Good Substrings

You are given a string s and must count the number of "good" substrings in it. A substring is considered good if:

• It has no repeating characters or
• It is a palindrome

Recall that a substring is a contiguous segment of the string. A palindrome is a string that reads the same forwards and backwards.

For example, for s = "abcd", there are 10 good substrings, and for s = "aaa", there are 6 good substrings.

Your task is to process multiple test cases. For each test case, output the number of good substrings in the given string.

The formula for the total number of substrings of a string of length \( n \) is given by \( \frac{n(n+1)}{2} \), although here you will only count those that meet the criteria above.

inputFormat

The first line contains an integer \( T \) representing the number of test cases.

The following \( T \) lines each contain a single string \( s \). The string may be empty.

outputFormat

For each test case, output a single line containing the number of good substrings for the corresponding string.

## sample

2
abcd
aaa

10
6

</p>