102377: [AtCoder]ABC237 Ex - Hakata

Problem Statement

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?

Notes

A substring of $S$ 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.

Constraints

• $1 \leq |S| \leq 200$
• $S$ consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the answer.

Sample Input 1

ababb

Sample Output 1

3

Three palindromes aba, bab, bb can be chosen.

Sample Input 2

xyz

Sample Output 2

3

Three palindromes x, y, z can be chosen.

Sample Input 3

xxxxxxxxxx

Sample Output 3

1

问题描述

我们有一个由小写英文字母组成的字符串$S$。
鲍勃每天都在思考回文。他决定从$S$中选择一些回文子串并告诉安娜。

如果鲍勃告诉安娜的回文子串中有一个是另一个的子串，安娜就会生气。

鲍勃可以在不惹安娜生气的情况下选择多少个回文子串呢？

注释

字符串$S$的 子串 是从$S$的开头和结尾删除零个或多个字符的结果。
例如，ab 是 abc 的子串，而 ac 不是 abc 的子串。

约束

• $1 \leq |S| \leq 200$
• $S$由小写英文字母组成。

输入

输入格式如下：

$S$

输出

打印答案。

样例输入1

ababb

样例输出1

3

可以选中3个回文子串aba、bab、bb。

样例输入2

xyz

样例输出2

3

可以选中3个回文子串x、y、z。

样例输入3

xxxxxxxxxx

样例输出3

1