Palindromes

A string is called a palindrome if it reads the same from left to right and from right to left. For example, the string "abba" is a palindrome, while "omax" is not. A substring of string $\alpha$ from position $i$ to position $j$ inclusive (positions are numbered from $1$) will be denoted as $\alpha [i..j]$. The length of such a substring is $j-i+1$.

For the given string $\alpha$ of length $n$, find the number $q$ of pairs $(i,j)$ such that $1\le i<j\le n$ and the substring $\alpha [i..j]$ is a palindrome.

Input

The input consists of a string $\alpha$ of length $n(1\le n\le 10^5)$, composed of lowercase Latin letters.

Output

Print the number of required pairs $q$.

Examples