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≥2) is one-and-half palindromic if and only if it satisfies  S[i]=S[2n−i]=S[2n+i−2](1≤i≤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.