题目描述

给定长为n的字符串(n<=500)，每次可以将连续一段回文序列消去，消去后左右两边会接到一起，求最少消去几次能消完整个序列。

输入格式

一行一个由小写字母组成的字符串。

输出格式

一个正整数，表示消去次数。

样例数据

input

asbasda

output

3

样例说明

“asbasda” -> “asasda” -> “asasa” -> “”

时间限制、数据范围及描述

对于 30%的数据：n<=10；
对于 60%的数据：n<=50；
对于100%的数据：n<=500。