问题1526--小L的项链切割

1526: 小L的项链切割

时间限制: 1 Sec  内存限制: 128 MB
提交: 114  解决: 41
[提交] [状态] [讨论版] [命题人:]
题目描述
小T送给了小L了一串项链。为了方便,我们把项链上形态不同钻石用不同的字母表示。这样小L的项链就变成了一个字符串。小L忽然想把这串项链优美地切割一下,她想把它切割成尽量少的回文项链,啊也就是回文串。求最少的切割次数。
输入

第一行一个整数T 表示数据组数

下面T组数据,每一组数据:

只有一行,一个只有小写英文字母的字符串,字符串长度 <= 1000。

输出
对于每一组数据,输出将这个字符串能切割成最少的回文串所需切割的次数。
样例输入 Copy
2
abaacca
abcd
样例输出 Copy
1
3
来源/分类