回文串

题目描述

小 $D$ 最近在学习回文串的有关知识。对于字符串 $S=S_1S_2S_3\cdots S_{n-1}S_n$，记 $S$ 的反串 $S^R=S_nS_{n-1}S_{n-2}\cdots S_2S_1$。我们称字符串 $S$ 是回文串，当且仅当 $S=S^R$。

小 $D$ 发现回文串很少，他决定定义一些新的东西。定义字符串 $S=S_1S_2S_3\cdots S_{n-1}S_n$ 和 $T=T_1T_2T_3\cdots T_{m-1}T_m$ 的和 为 $S_1S_2S_3\cdots S_{n-1}S_nT_1T_2T_3\cdots T_{m-1}T_m$，记作 $S\circ T$。

小 $D$ 发现，字符串之和满足结合律但不满足交换律，即 $(A\circ B)\circ C=A\circ (B\circ C)$ 成立，但 $A\circ B=B\circ A$ 不一定成立。

小 $D$ 定义字符串 $S$ 的一个拆分，为满足 $A_1\circ A_2\circ A_3\circ \cdots \circ A_L$ 的字符串序列 $A=[A_1,A_2,\cdots,A_L]$。定义这样的一个拆分的长度为 $L$。

小 $D$ 定义一个拆分的反拆分为序列 $A^R=[A_L,A_{L-1},\cdots,A_2,A_1]$。定义一个拆分是回文的，当且仅当 $A=A^R$（两个序列相等定义为同样位置的元素对应相等）。

小 $D$ 现在给出了字符串 $S$，想要求出 $S$ 的最长（即长度最大）的回文拆分序列有多长。请你帮帮他。

输入格式

本题包含多组数据，输入的第一行为一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行一个字符串，表示这组数据中的 $S$。保证 $S$ 仅有小写字母组成。

输出格式

对于每组测试数据，输出一行一个整数表示答案。

样例输入 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

见下发文件 ex_palindrome2.in/out。

数据规模与约定

本题共 $10$ 个测试数据，每个测试数据 $10$ 分。以下为部分分分布（$\lvert S\rvert$ 表示字符串 $S$ 的长度）：

对于前 $10\%$ 的数据，$1\le \lvert S\rvert \le 5$；
对于另 $20\%$ 的数据，$1\le \lvert S\rvert \le 30$；
对于另 $20\%$ 的数据，$1\le \lvert S\rvert \le 200$；
对于另 $20\%$ 的数据，$1\le \lvert S\rvert \le 2000$；
对于另 $20\%$ 的数据，$1\le \lvert S\rvert \le 10^5$；
对于 $100\%$ 的数据，$1\le T\le 20$，$1\le \lvert S\rvert \le 10^6$，保证 $S$ 仅有小写字母组成。

时间限制：$2\mathtt{s}$

空间限制：$512\mathtt{MB}$

样例数据

样例数据