给一个字符串， 要求把它分割成若干个子串，使得每个子串都是回文串。问最少可以分割成多少个。
例如：
“racecar”本身就是回文串，答案为1
“fastcar”，答案为7，分成的7个回文串为"f", "a", "s", "t", "c", "a", "r"
“aaadbccb”,答案为3，分成的3个回文串为"aaa", "d", "bccb"

一行，一个由小写字母构成的字符串，该字符串的长度不超过2000

一行，一个整数，表示最少分割出的回文串的个数。