Problem Description

For a string \( S \), Xiao Lu defines it as palindromic if and only if the string \( S \) reads the same forwards and backwards, for example, \(\tt abcba\) is palindromic, while \(\tt abcca\) is not.

Xiao Lu now has a string \( S \). He wants to divide this string into segments of lengths \( 1, 2, 3, \dots \). Specifically, he will first take the first character as string \( S_1 \), then the second and third characters as \( S_2 \), then the fourth, fifth, and sixth characters as \( S_3 \), and so on... If there are any remaining characters, they will be treated as a separate segment.

For example, for the string \(\tt aaababcaacd\), it 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 \);

All five strings derived from the segmentation of \(\tt aaababcaacd\) are palindromic.

Xiao Lu wants to know, for the input string \( S \), how many of these segmented strings are palindromic?

Input Format

Input consists of one line, a string \( S \).

Output Format

Output a single integer, representing the answer.

Sample Input and Output

Sample Input #1

aaababcaacd

Sample Output #1

5

Sample Input #2

abacdcaaba

Sample Output #2

2

Notes

[Sample Explanation]

• For the first sample, the explanation is provided in the problem statement;
• For the second sample, \( S_1 = \tt a \), \( S_2 = \tt ba \), \( S_3 = \tt cdc \), \( S_4 = \tt aaba \), where \( S_1 \) and \( S_3 \) are palindromic strings.

[Data Range]

Denote \( |S| \) as the length of string \( S \).

• For 10% of the data, the string contains at most one type of letter;
• For 30% of the data, the string contains at most two types of letters;
• For 70% of the data, \( |S| \leq 1000 \);
• For all data, \( 1 \leq |S| \leq 10^6 \), the string contains only lowercase English letters.

见题面 Input 部分

见题面 Output 部分