当前没有测试数据。

5.回文分区

题目描述

给出一个只包含小写字母字符串，要求你将它划分成尽可能多的小块，使得这些小块构成回文串。

例如：对于字符串$abcab$，将它分成$ab$ $c$ $ab$或者$abcab$就是构成回文串的划分方法，$abc$ $ab$则不是。

输入格式

第一行输入一个整数$T$表示数据组数。

接下来的$T$行，每行输入一个字符串，代表你需要处理的字符串，保证该字符串只包含小写字母。

输出格式

输出$T$行，对于每个输入的字符串，输出一行包含一个整数$x$，表示该字符串最多能分解成$x$个小块，使得这些小块构成回文串。

数据范围与提示

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

• 子任务$1$（$15\%$）：$1 \leq L \leq 30$；
• 子任务$2$（$20\%$）：$1 \leq L \leq 300$；
• 子任务$3$（$25\%$）：$1 \leq L \leq 10^4$；
• 子任务$4$（$40\%$）：无特殊限制。

样例

4
bonobo
deleted
racecar
racecars

3
5
7
1