CF7D.Palindrome Degree

String s of length n is called k-palindrome, if it is a palindrome itself, and its prefix and suffix of length are (k - 1)-palindromes. By definition, any string (even empty) is 0-palindrome.

Let's call the palindrome degree of string s such a maximum number k, for which s is k-palindrome. For example, "abaaba" has degree equals to 3.

You are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.

长度为 $n$ 的字符串 $s$ 被称为 $k$-回文串，当且仅当它本身是回文串，且其长度为 $\left\lfloor \frac{n}{2} \right\rfloor$ 的前缀和后缀均为 $(k-1)$-回文串。根据定义，任意字符串（包括空串）都是 0-回文串。

我们称字符串 $s$ 的回文度为满足 $s$ 是 $k$-回文串的最大整数 $k$。例如，字符串 "abaaba" 的回文度为 3。

给定一个字符串，你的任务是求出它所有前缀的回文度之和。

The first line of the input data contains a non-empty string, consisting of Latin letters and digits. The length of the string does not exceed 5·106. The string is case-sensitive.

输入数据的第一行包含一个非空字符串，该字符串仅由拉丁字母和数字组成。字符串长度不超过 $5 \cdot 10^6$。字符串区分大小写。

Output the only number — the sum of the polindrome degrees of all the string's prefixes.

输出唯一的数字——字符串所有前缀的回文度之和。