Count Palindrome Segments

Given a string \(S\), we define it as a palindrome if and only if reading \(S\) from left to right is the same as reading it from right to left. For example, \(\tt abcba\) is a palindrome, while \(\tt abcca\) is not.

You are provided with a string \(S\). The string is to be partitioned into segments of increasing lengths: the first segment \(S_1\) has length 1, the second segment \(S_2\) has length 2, the third segment \(S_3\) has length 3, and so on. In particular, you will extract the first character as \(S_1\), then the next 2 characters as \(S_2\), then the following 3 characters as \(S_3\), and so forth. If there are leftover characters that do not form a complete segment, they form the last segment on their own.

For example, for the string \(\tt aaababcaacd\), the segments are:

• \(S_1 = \tt a\)
• \(S_2 = \tt aa\)
• \(S_3 = \tt bab\)
• \(S_4 = \tt caac\)
• \(S_5 = \tt d\)

All five segments in this example are palindromes. Your task is to compute the number of segments that are palindromes.

inputFormat

The input consists of a single line containing the string \(S\). The string \(S\) consists of only English letters.

outputFormat

Output a single integer, the number of segments that are palindromes.

sample

aaababcaacd

5