Count Palindromic Substrings

Given a string ( s ), your task is to count the number of substrings of ( s ) that are palindromes. A palindrome is a string that reads the same forwards and backwards. For example, in the string "aaa", the palindromic substrings are: "a", "a", "a", "aa", "aa", "aaa" for a total of 6.

Note: A single character is considered a palindrome.

inputFormat

The input is read from standard input. It consists of a single line containing the string ( s ). The string may contain only lowercase/uppercase letters.

outputFormat

Output to standard output a single integer, which is the number of palindromic substrings in ( s ).## sample

abc

3