7335: ABC237 —— Ex - Hakata
[Creator : ]
Description
We have a string S consisting of lowercase English letters.
Bob just thinks about palindromes every day. He decided to choose some of the substrings of S that are palindromes and tell them to Anna.
Anna gets angry if one of the palindromes told by Bob is a substring of another.
How many palindromes can Bob choose while not making Anna angry?
For example, ab is a substring of abc, while ac is not a substring of abc.
Bob just thinks about palindromes every day. He decided to choose some of the substrings of S that are palindromes and tell them to Anna.
Anna gets angry if one of the palindromes told by Bob is a substring of another.
How many palindromes can Bob choose while not making Anna angry?
Notes
A substring of SS is the result of deleting zero or more characters from the beginning and the end of S.For example, ab is a substring of abc, while ac is not a substring of abc.
Input
Input is given from Standard Input in the following format:
$S$
$S$
Output
Print the answer.
Constraints
1≤∣S∣≤200
S consists of lowercase English letters.
S consists of lowercase English letters.
Sample 1 Input
ababb
Sample 1 Output
3
Three palindromes aba, bab, bb can be chosen.
Sample 2 Input
xyz
Sample 2 Output
3
Three palindromes x, y, z can be chosen.
Sample 3 Input
xxxxxxxxxx
Sample 3 Output
1