长度为 n 的字符串 s 称为 k-回文,如果它本身是回文,并且其长度 $$\left\lfloor n/2 \right\rfloor$$ 的前缀和后缀是 (k - 1)-回文。根据定义,任何字符串(甚至是空字符串)都是 0 回文。
我们将字符串 s 的回文度称为最大数 k,其中 s 是 k-回文。例如,“abaaba”的度数等于 3。
给你一个字符串。您的任务是找到其所有前缀的回文度数之和。
输入
输入数据的第一行包含一个非空字符串,由拉丁字母和数字组成。字符串长度不超过5·106。该字符串区分大小写。
输出
输出唯一的数字——所有字符串前缀的回数度之和。
示例
输入 #1
a2A
输出 #1
1
输入 #2
abacaba
输出 #2
6