Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4077
Periodic Palindrome

Time Limit: 1 Second      Memory Limit: 131072 KB

Chiaki has a string $\dots w w^r w w^r \dots$ with infinite length, where $w=w_1w_2\dots w_m$ and $w^r=w_m w_{m-1} \dots w_1$.

Chiaki cuts out a substring $s=s_1s_2\dots s_n$ ($m < n$) from the infinite string. And it's guaranteed $s$ contains $w$ or $w^r$ as a substring. She would like to know the number of pairs ($i,j$) where $1 \le i \le j \le n$ and $s_{i..j}$ is a possible value of $w$ or $w^r$.

Input

There are multiple test cases. The first line of input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains a string $s$ ($2 \le |s| \le 10^6$) consisting only of lowercase English letters.

It is guaranteed that the sum of $|s|$ in all cases does not exceed $10^6$.

Output

For each test case, output an integer denoting the answer.

Sample Input

1
aaa

Sample Output

5

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status