题目描述

给你一个字符串 $s$，请你将 $s$ 分割成一些子串，使每个子串都是回文串。求符合要求的最少分割次数。

输入格式

一行一个字符串 $s$，仅由小写英文字母组成。

输出格式

输出一行一个整数，表示将 $s$ 分割成若干回文子串所需的最少分割次数。

样例

aab

1

样例解释
只需一次分割就可将 $s$ 分割成 ["aa","b"] 这样两个回文子串。

baaaabaa

1

数据范围

• $1 \le |s| \le 2000$
• $s$ 仅由小写英文字母组成