Вам задана строка \(s\) длины \(n\), состоящая только из строчных букв латинского алфавита. Вы можете применять к строке следующую операцию: взять непрерывную подстроку этой строки, состоящий из одинаковых символов и удалить её. Например, после удаление подстроки bbbb из строки abbbbaccdd вы получите строку aaccdd.
Посчитайте минимальное количество операций, необходимое для удаления всей строки \(s\).
Выходные данные
В единственное строке выведите число — минимальное количество операций, необходимое для удаления всей строки \(s\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
abaca
|
3
|
|
2
|
8
abcddcba
|
4
|