4214. [CEOI2017]回文块

【题目描述】

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

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

【输入格式】

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

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

【输出格式】

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

【样例1输入】

4
bonobo
deleted
racecar
racecars

【样例1输出】

3
5
7
1

【样例1说明】

bo no bo
d e let e d
r a c e c a r
racecars

【样例2输入输出】

下载样例2

【数据规模与约定】

对于 $100\%$ 的数据，$1 \leq T \leq 10$，每行字符串的长度 $n$ 符合 $1 \leq n \lt 5*10^6$。

测试点 $1 \sim 4：n \leq 30$

测试点 $5 \sim 8：n \leq 300$

测试点 $9 \sim 12：n \leq 10000$

测试点 $13 \sim 16：n \leq 5*10^6$

【来源】

CEOI2017