Count Substrings with Same Start and End Character

Given a string s, your task is to count the number of substrings that start and end with the same character. A substring is defined as a contiguous sequence of characters in the string.

For example, consider the string \( s = \texttt{abcab} \). The valid substrings that start and end with the same character are:

• \( \texttt{a} \) (first character)
• \( \texttt{abca} \)
• \( \texttt{abcab} \)
• \( \texttt{b} \) (second character)
• \( \texttt{c} \)
• \( \texttt{a} \) (fourth character)
• \( \texttt{b} \) (fifth character)

The answer for \( s = \texttt{abcab} \) is therefore 7.

Note that the result can be computed via a direct iterative approach or by using the formula:

\[ \text{Result} = \sum_{c \in \text{set of characters}} \frac{n_c \times (n_c+1)}{2} \]

where \( n_c \) denotes the number of occurrences of character \( c \) in the string. In this problem, you are expected to implement the iterative method.

inputFormat

The first line of input contains an integer T, representing the number of test cases.

Each of the following T lines contains a non-empty string s consisting of lowercase English letters.

outputFormat

For each test case, output a single line containing an integer which is the number of substrings of s that start and end with the same character.

## sample

2
abcab
aaa

7
6

</p>