U630958 总有人与我不期而遇在迷茫的路口

多年之后当夏天再次来到 我是否还能再听见你歌唱

给定一个仅由小写字母组成的字符串 $s$，我们称一个字符串的 **border** 为既是它的前缀又是它的后缀的非空也非本身的字符串。例如，字符串 `"abcab"` 的一个 border 为 `"ab"`，但请注意 `"abcab"`并不是border，而是该字符串本身 现在请你求出字符串 $s$ 的 **最长 border** 的长度。

输入包含多组测试数据。 第一行一个整数 $T$，表示测试组数。 接下来 $T$ 组数据，每组输入一行字符串 $s$。 - |s| 表示字符串 s 的长度。 - $1 \le T \le 1000$ - $1 \le |s| \le 3000 $ - $\sum|s| \le 3000$ - 每个 $s_i$ 仅由小写英文字母组成。

对于每组测试数据，输出一个整数，表示字符串 $s_i$ 的最长 border 的长度。