划分成回文串 Partitioning by Palindromes

题意翻译

回文子串(palind) **问题描述：** 当一个字符串正序和反序是完全相同时，我们称之为“回文串”。例如“racecar”就是一个回文串，而“fastcar”就不是。现在给一个字符串s，把它分割成若干个互不相交的回文子串，求分割的回文子串的最少个数。 **输入格式：** 第一行为正整数t(≤10)，表示数据组数；接下来t行，每行一个完全由小写字母组成的字符串，长度不超过1000。 **输出格式：** 对于每组数据，输出最少回文子串数。由 @C919 提供翻译

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2631 [PDF](https://uva.onlinejudge.org/external/115/p11584.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11584/b58c9dcfa5d68a9133bad9ac66ec6f0075a41624.png)

输入输出格式

输入格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11584/ebdb40e082de0cf7f7e568bd3d68026ae5b0d546.png)

输出格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11584/3c6a4208b8b9c7938aae2730af2cf6dc2ec6d48b.png)

输入输出样例

输入样例 #1

3
racecar
fastcar
aaadbccb

输出样例 #1

1
7
3