The string is a palindrome if it reads the same both left to right and right to left. For example, "abba" is a palindrome, and "omax" is not. Lets for a string α denote α [i .. j] the substring of length j - i + 1 from the i-th to the j-th position inclusive (the positions are numbered starting with 1).

For the given string α of length n find the number q of pairs (i, j), 1 ≤ i < j ≤ n, such that α[i..j] is a palindrome.

Input

The string α of length n (1 ≤ n ≤ 105), that consists of small Latin letters.

Output

The number of pairs q.