
ZOJ Problem Set  4077
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_{m1} \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$. InputThere 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$. OutputFor each test case, output an integer denoting the answer. Sample Input1 aaa Sample Output5 Author: LIN, Xi Source: Yet Another Xi Lin Contest 