Count Substrings with Matching Endpoints

You are given a string s and your task is to count all substrings of s that start and end with the same character. A substring is a contiguous block of characters in s.

Specifically, for a string of length n, consider all pairs of indices \( (i,j) \) such that \( 0 \leq i \leq j < n \) and the condition s[i] = s[j] holds. Each such pair defines a valid substring.

The mathematical formulation can be seen as: \[ \text{Answer} = \sum_{i=0}^{n-1}\sum_{j=i}^{n-1} \mathbf{1}_{\{s[i]=s[j]\}}, \] where \( \mathbf{1}_{\{condition\}} \) equals 1 when the condition is true, and 0 otherwise.

Your task is to write a program that processes multiple test cases. For each test case, output the number of valid substrings. The input will be read from standard input and the output should be printed to standard output.

inputFormat

The first line of input contains a single integer T representing the number of test cases. The following T lines each contain a string s. Note that the string may be empty.

outputFormat

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

## sample

2
abc
aaa

3
6

</p>