迷之回文

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

FF最近喜欢上了回文串,比如aaaba都是回文串,今天FF有了一个奇葩的想法。

对于给定的一个字符串S(仅有小写英文字母组成,|S| <= 100000)FF想知道S的前缀中有多少个是回文串。

如,ababa,前缀”a”,”aba”,”ababa”都是回文串。

Input

 多组输入。每组数据一个字符串S

Output

 对于每组数据输出一个数代表答案。

Sample Input

ababa
abcde

Sample Output

3
1

Hint

 

Source

zmx