g6-07905. 分割回文串 未做

给定一个字符串 $s$。把 $s$ 分割成若干连续段，要求每一段都是回文串。求最少切割次数（段数减一）。

一行一个字符串 $s$。

一行一个整数，表示最少切割次数。

输入 1

aab

输出 1

1

对于所有数据，$1\le |s|\le 2000$。