Hakata

题目描述

给定一个由小写英文字母组成的字符串 $S$。

高桥博多每天都在思考回文。他决定从 $S$ 的子串中选择若干个是回文串的子串，并把它们告诉小仓楽子。

如果被告知的回文串中存在两个回文串，使得其中一个是另一个的子串，小仓楽子就会生气。

在不让小仓楽子生气的前提下，高桥博多最多可以选择多少个回文串？

注记

字符串 $S$ 的子串，是指从 $S$ 的开头删除 $0$ 个或多个字符、从结尾删除 $0$ 个或多个字符后得到的字符串。

例如，ab 是 abc 的子串，而 ac 不是 abc 的子串。

输入格式

输入从标准输入给出，格式如下：

S

输出格式

输出最多可以选择的回文串个数。

数据范围

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

样例

样例输入 1

ababb

样例输出 1

3

样例输入 2

xyz

样例输出 2

3

样例输入 3

xxxxxxxxxx

样例输出 3

1

样例说明

• 样例 1 中，可以选择 aba、bab、bb 这 $3$ 个回文串。
• 样例 2 中，可以选择 x、y、z 这 $3$ 个回文串。
• 样例 3 中，由于所有回文串都互相存在包含关系，最多只能选择 $1$ 个。