Palindrome

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description

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.

Input

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.

Output

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

Sample Input

1 ababcbabccbaabc

Sample Output

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

Hint

jiangzijing2015

Source

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

提交代码