Palindrome

Alice like strings, especially long strings. For each string, she has a special evaluation system to judge how elegant the string is. She defines that a string $S[1..3n-2](n \geq 2)$ is one-and-half palindromic if and only if it satisfies $S[i]=S[2n-i]=S[2n+i-2] (1\leq i \leq n)$.For example, $abcbabc$ is one-and-half palindromic string, and $abccbaabc$ is not. Now, Alice has generated some long strings. She ask for your help to find how many substrings which is one-and-half palindromic.

The first line is the number of test cases. For each test case, there is only one line containing a string(the length of strings is less than or equal to $500000$), this string only consists of lowercase letters.

For each test case, output a integer donating the number of one-and-half palindromic substrings.

1
ababcbabccbaabc

2

In the example input, there are two substrings which are one-and-half palindromic strings, $abab$ and $abcbabc$.

2017中国大学生程序设计竞赛-哈尔滨站-重现赛（感谢哈理工）