Migrated from Lutece 1026 How many good substrings

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Icerain likes strings very much. Especially the strings only consist of 0 and 1,she call them easy strings. One day, she is so boring that she want to find how many good substrings in an easy string?

A good substring is a substring which can be a palindrome string after you change any two characters' positions(you can do this operation any times).For example,$100$ is a good substring of $1001$,beacuse you can change it to be $010$,which is a palindrome string.

Input

The first line is the number of test cases. (no more than $100$)

Each test case has one line containing one string only consist of 0 and 1. The length of the string is no greater than $100000$.

Output

For each test case, output one line contains the number of good substrings.

Samples

2
01
01101

2
11

Resources

Fantasy