Count the number of palindrome substrings of a given string S.
A substring of S is a string that can be obtained from S by removing some (possibly zero) characters from the beginning of S and some (possibly zero) characters from the end of S.
### Input
- 1 line contains string S.
### Output
- The number of palindrome substrings of S.
### Constraints
- 1≤|S|≤105.
### Example
Input:
mima
Output:
5