Palindromic Counter :
Difficulty Level : Medium
Submissions : 344
Asked In :
Marks :100
: 7 | : 0
A palindromic is a string that reads the same from the left and from the right. For example, mom and tacocat are palindromes, as are any single characters string .Given a string determines the number if substrings that are palindromes.
Input
The first line of input contains a string s .($$$1 \le S \le 5000$$$)
Output
For each test case print the number of palindromes substring
Example
Input
tacocat
Output
10
Note
Example:
The string is s=tacocat. Palindromic substrings are [t,a,c,o,c,a,t,coc,acoca,tacocat].
There are total of 10 palindromic substrings.
