A93035.「LNOI2022」串

为了让你更好地理解题面，给出若干关于字符串的定义：

• 对于一个字符串 $S = s_1 s_2 \cdots s_n$，定义其长度为 $\lvert S \rvert = n$。
• 对于两个字符串 $S = s_1 s_2 \cdots s_n$ 和 $T = t_1 t_2 \cdots t_m$，称 $T$ 为 $S$ 的子串，若 $m = 0$（即 $T$ 为空串）或者 $\exists 1 \le i \le j \le n$，$T = s_i s_{i + 1} \cdots s_j$。若 $m = 0$ 或上述判断条件中 $i$ 可以取到 $1$，则称 $T$ 为 $S$ 的前缀；若 $m = 0$ 或上述判断条件中 $j$ 可以取到 $n$，则称 $T$ 为 $S$ 的后缀。

给定一个英文小写字母构成的字符串 $S$，你需要找到一个尽可能长的字符串序列 $(T_0, T_1, \ldots, T_l)$，满足：

• $T_0$ 是 $S$ 的子串；
• $\forall 1 \le i \le l$，$\lvert T_i \rvert - \lvert T_{i - 1} \rvert = 1$；
• $\forall 1 \le i \le l$，存在 $S$ 的一个长度为 $\lvert T_i \rvert + 1$ 的子串 $S'_i$，使得 $S'_i$ 的长度为 $\lvert T_{i - 1} \rvert$ 的前缀为 $T_{i - 1}$，长度为 $\lvert T_i \rvert$ 的后缀为 $T_i$。

输出这样的字符串序列的长度的最大值（即 $l$ 的最大值）。

本题有多组测试数据。输入的第一行为一个整数 $T$，表示测试数据组数。对于每组测试数据，输入一行一个英文小写字母构成的字符串 $S$。

对于每组测试数据输出一行一个整数，表示题目描述中字符串序列长度的最大值。