String Magic (Easy Version)

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)$.

Sample Input

3
aaaa
abaaba
ababa

Sample Output

4
2
0

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）