回文划分

题目限制

3000 ms 256 M

题目描述

给出一个小写英文字母字符串，要请你将它划分成尽量多的短串，使得它们构成回文串。回文串的定义是，所有位置对称的短串相同。例如，可以把 $abcab$ 分成 $ab,c,ab$ ，我们认为这是一种长度为 $3$ 的划分方案。

输入格式

第一行输入一个整数 T 表示数据组数。
接下来的 T 行，每行输入一个字符串，代表你需要处理的字符串，保证该字符串只包含小写字母。 其中1≤T≤10，字符串长度≤1e6。

输出格式

输出 T 行，对于每个输入的字符串，输出一行表示最多能分成多少短串。

数据范围

对于 $100\%$ 的数据，有 $1\le T\le 10$ 。设 $L$ 为单个字符串的长度，则 $1\le L\le 10^6$ 。

子任务 $1$ : $1\le L\le 30$ ；

子任务 $2$ : $1\le L\le 300$ ；

子任务 $3$ : $1\le L\le 10^4$ ；

子任务 $4$ : 无特殊限制。

输入样例

4
bonobo
deleted
racecar
racecars

输出样例

3
5
7
1

样例解释

对于 $bonobo$，分段为：$bo$, $no$, $bo$