{"raw_statement":[{"iden":"statement","content":"为了让你更好地理解题面，给出若干关于字符串的定义：\n\n- 对于一个字符串 $S = s_1 s_2 \\cdots s_n$，定义其长度为 $\\lvert S \\rvert = n$。\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$ 的后缀。\n\n给定一个英文小写字母构成的字符串 $S$，你需要找到一个尽可能长的字符串序列 $(T_0, T_1, \\ldots, T_l)$，满足：\n\n- $T_0$ 是 $S$ 的子串；\n- $\\forall 1 \\le i \\le l$，$\\lvert T_i \\rvert - \\lvert T_{i - 1} \\rvert = 1$；\n- $\\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$。\n\n输出这样的字符串序列的长度的最大值（即 $l$ 的最大值）。"},{"iden":"input","content":"**本题有多组测试数据**。输入的第一行为一个整数 $T$，表示测试数据组数。对于每组测试数据，输入一行一个英文小写字母构成的字符串 $S$。"},{"iden":"output","content":"对于每组测试数据输出一行一个整数，表示题目描述中字符串序列长度的最大值。"},{"iden":"note","content":"**【样例解释 \\#1】**\n\n下文中使用符号 $\\epsilon$ 表示空串。\n\n对于第一组测试数据，可以找到如下字符串序列：$T_0 = \\epsilon, T_1 = \\texttt{b}, T_2 = \\texttt{cd}$，其中 $S'_1 = \\texttt{ab}, S'_2 = \\texttt{bcd}$。\n\n对于第二组测试数据，可以找到如下字符串序列：$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}$。\n\n对于第三组测试数据，可以找到如下字符串序列：$T_0 = \\epsilon$。\n\n**【样例 \\#2】**\n\n见附件中的 `string/string2.in` 与 `string/string2.ans`。\n\n该组样例中的字符串长度有一定梯度，你可以利用该组样例对程序进行检查。\n\n**【样例 \\#3】**\n\n见附件中的 `string/string3.in` 与 `string/string3.ans`。\n\n该组样例满足特殊性质 A。\n\n**【数据范围】**\n\n设 $\\sum |S|$ 表示测试点中所有测试数据的字符串长度和。\n\n对于 $100 \\%$ 的测试数据，$T \\ge 1$，$1 \\le \\lvert S \\rvert \\le 5 \\times {10}^5$，$1 \\le \\sum \\lvert S \\rvert \\le 1.5 \\times {10}^6$。\n\n| 测试点编号 | $\\lvert S \\rvert \\le$ | $\\sum \\lvert S \\rvert \\le$ | 特殊性质 |\n|:-:|:-:|:-:|:-:|\n| $1 \\sim 2$ | $30$ | $150$ | 无 |\n| $3 \\sim 5$ | $200$ | $800$ | 无 |\n| $6 \\sim 8$ | $1000$ | $3000$ | 无 |\n| $9 \\sim 11$ | $5 \\times {10}^5$ | $1.5 \\times {10}^6$ | A |\n| $12 \\sim 15$ | $6 \\times {10}^4$ | $3 \\times {10}^5$ | 无 |\n| $16 \\sim 20$ | $5 \\times {10}^5$ | $1.5 \\times {10}^6$ | 无 |\n\n特殊性质 A：字符串中的每个字符在小写字母中独立均匀随机生成。\n\n**【提示】**\n\n本题输入输出量较大，请使用较为快速的输入输出方式。\n\n例如，若你的代码使用了 `cin` 和 `cout` 作为输入输出方式，你可以选择在代码的**输入输出重定向语句**（`freopen` 语句、 `fopen` 语句等）**之后**加入以下语句加速输入输出速度。\n\n```cpp\nios::sync_with_stdio(0); cin.tie(0); cout.tie(0);\n```\n\n**加入该语句后不建议同时使用 `cin, cout` 和其他输入输出方式。**"}],"translated_statement":null,"sample_group":[["3\nabcd\nabab\na\n","2\n3\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}