# 3415. 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]$ is one-and-half palindromic if and only if it satisfies $S[i]=S[2n-i]=S[2n+i-2]$ $(1 \le i \le 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.

### 输入格式

There is only one line containing a string (the length of string is less than or equal to $500~000$). The string only consists of lowercase letters.

### 输出格式

Output an integer denoting the number of one-and-half palindromic substrings.

### 样例

Input
abcbabc

Output
1

Input
abccbaabc

Output
0

Input
ababcbabccbaabc

Output
2


4 人解决，6 人已尝试。

5 份提交通过，共有 13 份提交。

7.7 EMB 奖励。