Count Substrings with Identical Start and End

Given a string s consisting of lowercase letters, your task is to count the number of substrings that start and end with the same character. Note that single characters are considered valid substrings. The mathematical formula to calculate the number of such substrings for a character appearing n times is given by (\frac{n(n+1)}{2}). This problem tests your ability to process strings and apply combinatorial counting techniques.

inputFormat

The input begins with a single integer T on the first line, representing the number of test cases. The following T lines each contain a string s consisting of lowercase letters (possibly empty).

outputFormat

For each test case, output a single integer on a new line representing the number of substrings that start and end with the same character.## sample

2
abc
aaa

3
6