CF1948D Tandem Repeats?

给定一个由**小写字母**和**问号** `?` 组成的字符串 $s$，你可以将问号 `?` 替换为任何小写字母。 替换后，你需要找到 $s$ 中最长的**重复**子串。 一个长度为 $2n$ 的字符串 $t$ 是**重复**串，当且仅当对于所有 $1 \leq i \leq n$，有 $t_i = t_{i+n}$。

**本题目含多组数据。** 第一行，一个正整数 $t$，表示数据组数。 接下来每组数据仅包含一行，一个字符串 $s$。

对于每组数据，输出一行一个非负整数，表示你得到的最长重复子串的长度。 如果这样的子串不存在，输出 `0`。

对于 $100 \%$ 的数据，保证 $1 \leq t \leq 10^3, 1 \leq |s| \leq 5 \times 10^3$​。 保证 $\sum |s| \leq 5 \times 10^3$。 Translated by ShiRoZeTsu.