H. Help Eevee Pls Eh
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Eevee recently learned that its name is a palindrome! This means that it reads the same forward and backward.

However, Eevee is sad to discover that not many words are palindromes. One day, Eevee was visited by a friend. Upon hearing the friend's name, Eevee became curious.

Eevee wondered how many different ways there are to remove a single character from the friend's name so that the remaining characters, when concatenated, form a palindrome.

For example, in eevaee, removing either v or a is valid, but removing any of the e's is not.

We define a palindrome as the following: Given a string $$$S = s_1s_2\dots s_n$$$, we pair $$$(s_1, s_n)$$$, $$$(s_2, s_{n-1})$$$, $$$\dots$$$, $$$(s_{\lfloor \frac{n}{2}\rfloor}, s_{\lfloor \frac{n}{2}\rfloor + 1})$$$. $$$S$$$ is a palindrome if and only if in all of these $$$\lfloor \frac{n}{2}\rfloor$$$ pairs the characters in the pairs are identical.

Input

The first line of input contains an single string $$$S$$$ ($$$2 \leq |S| \leq 10^6$$$), the friend's name consisting of lowercase English letters a to z.

Output

Output a single integer representing the number of ways to remove a character from $$$S$$$ such that it becomes a palindrome.

Examples
Input
eevaee
Output
2
Input
helpeeveeplseh
Output
1
Note

For the string eevaee$$$ = s_1s_2s_3s_4s_5s_6$$$, if we simulate removing each character:

Removing $$$s_1$$$: We have pairs $$$(s_2, s_6), (s_3, s_5)$$$, $$$1$$$ of these pairs are identical.

Removing $$$s_2$$$: We have pairs $$$(s_1, s_6), (s_3, s_5)$$$, $$$1$$$ of these pairs are identical.

Removing $$$s_3$$$: We have pairs $$$(s_1, s_6), (s_2, s_5)$$$, $$$2$$$ of these pairs are identical.

Removing $$$s_4$$$: We have pairs $$$(s_1, s_6), (s_2, s_5)$$$, $$$2$$$ of these pairs are identical.

Removing $$$s_5$$$: We have pairs $$$(s_1, s_6), (s_2, s_4)$$$, $$$1$$$ of these pairs are identical.

Removing $$$s_6$$$: We have pairs $$$(s_1, s_5), (s_2, s_4)$$$, $$$1$$$ of these pairs are identical.

Thus, only for 2 of the characters is the number of valid pairs $$$\lfloor \frac{5}{2}\rfloor = 2$$$, thus the answer is $$$2$$$.