Count Substrings with Matching Endpoints

You are given several binary strings. For each binary string, your task is to count the number of substrings that start and end with the same character. A substring is a contiguous sequence of characters within the string. Note that a substring of length 1 (i.e. a single character) is valid as it trivially starts and ends with the same character.

To solve this problem, observe that for a given character (either '0' or '1'), if it appears ( n ) times in the string, the number of substrings that begin and end with that character is given by the formula:

[ \frac{n \times (n+1)}{2} ]

The final answer for a binary string is the sum of the counts for '0' and '1'.

inputFormat

The first line contains a single integer ( T ) denoting the number of test cases. Each of the following ( T ) lines contains a binary string consisting only of the characters '0' and '1'.

outputFormat

For each test case, output a single line containing the number of substrings which start and end with the same character.## sample

3
10101
11111
000

9
15
6