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..3n2](n≥2) is one-and-half palindromic if and only if it satisfies S[i]=S[2ni]=S[2n+i2] .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.
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.
（图片来源网络，侵删）
