4491: 「CEOI2017」Palindromic Partitions
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给出一个只包含小写字母字符串，要求你将它划分成尽可能多的小块，使得这些小块构成回文串。
例如：对于字符串 ``abcab``，将他分成 ``ab`` ``c`` ``ab`` 或者 ``abcab`` 就是构成回文串的划分方法，``abc`` ``ab`` 则不是。
输入
第一行输入一个整数 $T$ 表示数据组数。
接下来的 $T$ 行，每行输入一个字符串，代表你需要处理的字符串，保证该字符串只包含小写字母。
输出
输出 $T$ 行，对于每个输入的字符串，输出一行包含一个整数 $x$，表示该字符串最多能分解成 $x$ 个小块，使得这些小块构成回文串。
样例输入 复制
4
bonobo
deleted
racecar
racecars样例输出 复制
3
5
7
1提示
数据范围：对于 $100\%$ 的数据，有 $1\le T\le 10$。设 $L$ 为单个字符串的长度，则 $1\le L\le 10^6$。 + 子任务 1（$15\%$）: $1\le L\le 30$； + 子任务 2（$20\%$）: $1\le L\le 300$； + 子任务 3（$25\%$）: $1\le L\le 10^4$； + 子任务 4（$40\%$）: 无特殊限制。