测试数据来自 system/3072

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　给定一个字符串，每一次你可以挑选其中的一个回文子串消除，消除后其左右两部分字符串重新连接成一个新串。那么最少几次就可以把这个字符串全部消除。

【输入格式】

　　若干行，每行一个待消除的字符串。

【输出格式】

　　若干行，每行输出一个答案，表示消除对应输入的字符串的最少消除次数。

【输入输出样例】

　Input

aba
abc
addbcba

　Output

1
3
2

【样例解释】

　　第一个字符串 "aba" 就是一个回文串，一次可以把全部字符消除
　　第二个字符串 "abc" ，每次消除一个字符，需要三次才能全部消除
　　第三个字符串 "addbcba" ，分两次消除，先消除子串 "dd"，再消除 "abcba"。

【数据限制】

　　\(100\%\) 的数据：字符串长度不超过100。

【来源】

　Mr.he