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 \le |S| \le 10^5$.
### Example
Input:
```
mima
```
Output:
```
5
```