Suffix passport control#8249

Suffix passport control

1 second
512 megabytes
Hard

The team from Uzlandia is visiting Venice this year, the host of the world programming semi-final.At the passport control in this city-country, a string of length is checked as follows:For each position in the range , the string formed by + is examined to see if it is a palindrome. Here, represents the suffix of the string starting from position (inclusive), with positions numbered from zero. The suffix can be empty. is the reverse of the string , and "+" denotes the concatenation of two strings.Your task is to determine how many positions result in the aforementioned string being a palindrome.

Input

The input consists of a single line containing a string with a length of no more than 10^6.

Output

Output a single integer, which is the solution to the problem.

Examples

Example 1

Loading
Loading