小L的项链切割 - Problem

Problem4952--小L的项链切割

_{[Creator : ]}

Time Limit : 1.000 sec Memory Limit : 256 MiB

小 T 送给了小 L 了一串项链。为了方便，我们把项链上形态不同钻石用不同的字母表示。这样小 L 的项链就变成了一个字符串。小 L 忽然想把这串项链优美地切割一下，她想把它切割成尽量少的回文项链，啊也就是回文串。求最少的切割次数。

第一行一个整数 T 表示数据组数
下面 T 组数据，每一组数据:
只有一行，一个只有小写英文字母的字符串，字符串长度 <= 1000。

对于每一组数据，输出将这个字符串能切割成最少的回文串所需切割的次数。

2
abaacca
abcd

1
3

Submit