题目描述

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

• 对于一个字符串 $S = s_1 s_2 \cdots s_n$，定义其长度为 $|S| = 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)$，满足：

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

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

---

输入格式

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

---

输出格式

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

---

样例 1

输入

3
abcd
abab
a

输出

2
3
0

下文中使用符号 $\epsilon$ 表示空串。

• 对于第一组测试数据，可以找到如下字符串序列：$T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{cd}$，其中 $S'_1 = \texttt{ab}, S'_2 = \texttt{bcd}$。
• 对于第二组测试数据，可以找到如下字符串序列：$T_0 = \epsilon, T_1 = \texttt{b}, T_2 = \texttt{ab}, T_3 = \texttt{bab}$，其中 $S'_1 = \texttt{ab}, S'_2 = \texttt{bab}, S'_3 = \texttt{abab}$。
• 对于第三组测试数据，可以找到如下字符串序列：$T_0 = \epsilon$。

---

样例 2

见附加文件中 string2.in 和 string2.ans。

该组样例中的字符串长度有一定梯度，你可以利用该组样例对程序进行检查。

---

样例 3

见附加文件中 string3.in 和 string3.ans。

该组样例满足特殊性质 A。

---

数据范围

设 $\sum |S|$ 表示测试点中所有测试数据的字符串长度和。

对于 $100\%$ 的测试数据，$T \geq 1$，$1 \leq |S| \leq 5 \times 10^5$，$1 \leq \sum |S| \leq 1.5 \times 10^6$。

| 测试点编号 | $|S| \leq$ | $\sum |S| \leq$ | 特殊性质 | |:----------:|:---------:|:-----------:|:--------:| | 1 ~ 2 | 30 | 150 | 无 | | 3 ~ 5 | 200 | 800 | 无 | | 6 ~ 8 | 1000 | 3000 | 无 | | 9 ~ 11 | $5 \times 10^5$ | $1.5 \times 10^6$ | A | | 12 ~ 15 | $6 \times 10^4$ | $3 \times 10^5$ | 无 | | 16 ~ 20 | $5 \times 10^5$ | $1.5 \times 10^6$ | 无 |

特殊性质 A：字符串中的每个字符在小写字母中独立均匀随机生成。

提示

本题输入输出量较大，请使用较为快速的输入输出方式。

例如，若你的代码使用了 cin 和 cout 作为输入输出方式，你可以选择在代码的输入输出重定向语句（freopen 语句、fopen 语句等）之后加入以下语句加速输入输出速度。

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

加入该语句后不建议同时使用 cin、cout 和其他输入输出方式。