The palindrome is a string longer than one character, that reads the same right to left and left to right. The super palindrome is a string that can be represented as a concatenation of one or more palindromes. Given the string S. Find the number of substrings in S that are super palindromes.

Input

One string S contains a sequence of length from 1 to 1000 lowercase Latin letters without spaces.

Output

Print one number - the number of substrings of S that are super palindromes.