题目描述

给定一个仅包含小写字母的字符串 $s$，每次你可以选出一个回文子串，并将其删去；此时余下的字符串会自动前后拼接成一个新的字符串。

请问，最少需要多少步才能将原字符串全部删完？

输入格式

输入共一行，一个字符串 $s$

输出格式

输出共一行， 一个正整数表示答案

iai

1

iaa

2

数据范围

设 $|s|$ 为给定字符串 $s$ 的长度

• 对于 $30\%$ 的数据， $1 \leq |s| \leq 10$
• 对于 $60\%$ 的数据， $1 \leq |s| \leq 100$
• 对于 $100\%$ 的数据， $1 \leq |s| \leq 500$