该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

For a string $S$, Timothy defines it as a palindrome if and only if every character index $i$ in the string $S$ of length $x$ satisfies $S[i]=S[x-1-i]$. For example, $\tt abcba$ is a palindrome because $S[0]=S[4], S[1]=S[3], S[2]=S[2]$, while $\tt abcca$ is not.

Timothy now has a string $S$ and wants to divide it into several segments of length $1, 2, 3, and \dots$. Specifically, he will first take the first character and make it $S_1$, then take the $2nd, 3rd$ characters and make it $S_2$, then take the $4th, 5th, 6th$ characters and make it $S_3$, and so on... Finally, if there are any extra characters, they will be treated as separate segments.

For example, the string $\tt aaababcaacd$ will be divided into the following five strings:

• $S_1=\tt a$;
• $S_2=\tt aa$;
• $S_3=\tt bab$;
• $S_4=\tt caac$;
• $S_5=\tt d$;

The $5$ strings split from the string $\tt aaababcaacd$ are all palindromes.

Timothy wants to know, for the input string $S$, how many of the split strings are palindromes?

Input

Input a line, a string $S$. Its length $x$ satisfies $1 \leq x \leq 10^6$, and the string contains only English lowercase letters

Output

Output an integer representing the answer.

Samples

aaababcaacd

5

abacdcaaba

2

Notes

For the first group of examples, they have been described in the question;

For the $2$-nd group of examples, $S_1=\tt a$, $S_2=\tt ba$, $S_3=\tt cdc$, $S_4=\tt aaba$, where $S_1$ and $S_3$ are palindrome strings.