题目描述

对于一个字符串 $S$，如果从左往右读和从右往左读一样，则认为$S$是 回文 的，例如 $\tt abcba$ 是回文的，而 $\tt abcca$ 不是。

现有一个字符串 $S$，将这个字符串分为若干段，段长度分别为 $1,2,3,\dots$。具体而言，他会先将第一个字符拿出来作为字符串 $S_1$，再将第 $2,3$ 个字符拿出来作为 $S_2$，再将第 $4,5,6$ 个字符拿出来作为 $S_3$，以此类推……最后若还有多余的字符，则单独作为一段。

例如说，对于字符串 $\tt aaababcaacd$，会被分为如下的五个字符串：

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

字符串 $\tt aaababcaacd$ 分割出的 $5$ 个字符串都是回文的。 对于读入的字符串 $S$，这些被分割出来的字符串，有多少个是回文的呢？

输入格式

输入一行，一个字符串 $S$。

输出格式

输出一个整数，表示答案。

样例 #1

样例输入 #1

aaababcaacd

样例输出 #1

5

样例 #2

样例输入 #2

abacdcaaba

样例输出 #2

2

提示

【样例解释】

• 对于第 $1$ 组样例，已经在题面中进行表述；
• 对于第 $2$ 组样例，$S_1=\tt a$，$S_2=\tt ba$，$S_3=\tt cdc$，$S_4=\tt aaba$，其中 $S_1$ 与 $S_3$ 为回文字符串。

【数据范围】

假定记号 $|S|$ 表示字符串 $S$ 的长度。

• 对于 $10\%$ 的数据，字符串至多包含一种字母；
• 对于 $30\%$ 的数据，字符串至多包含两种字母；
• 对于 $70\%$ 的数据，$|S|\leq 1000$；
• 对于所有数据，$1 \leq |S| \leq 10^6$，字符串仅包含英语小写字母。