Problem Description

Z is learning string theory and he finds a difficult problem.

Given a string $S$ of length $n$ (indexed from $1$ to $n$) , define $f(S)$ equal to the number of pair $(i,j)$ that:

- $1 \le i < j \le n$

- $j-i+1=2k, k>0$ ($j-i+1$ is even)

- $S[i,i+k-1]=S[i+k,j]$

- $S[i,i+k-1]$ is a palindrome

Here $S[L,R]$ denotes the substring of $S$ with index from $L$ to $R$.

A palindrome is a string that reads the same from left to right as from right to left.

To solve this problem, Z needs to calculate $f(S)$.

He doesn't know how to solve it, but he knows it's easy for you. Please help him.

Input

The first line contains one integer $T\ (1\le T\le 10)$ which represents the number of test cases.

For each test case: One line contains a string $S\ (1\le |S| \le 10^5)$.

It's guaranteed that the string only contains lowercase letters.

Output

For each test case: Print one line containing one integer which represents $f(S)$.

3
aaaa
abaaba
ababa

4
2
0