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.
The input consists of a single line containing a string with a length of no more than 10^6.
Output a single integer, which is the solution to the problem.
Example 1