Migrated from Lutece 1386 卿大爷的三个女友

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

卿大爷发现了一个字符串，他要在上面找到$3$个女朋友的名字。他的一个女朋友名字是字符串的前缀，一个是后缀，还有一个在中间的某个位置（三者不互相重叠）。他想让你告诉他他女朋友名字的最大长度是多少。也就是说找到一个最长的子串使得它既是前缀又是后缀，还在中间，求这个子串的长度。

Input

第一行一个数字$N（N<=100)$,代表有N组数据。 接下来N行，每行一个字符串$s，1<=|s|<=100000$，均由小写字母构成。

Output

对于每组数据，输出最长符合条件子串的长度。

Samples

5
xy
abc
aaa
aaaaba
aaxoaaaaa

0
0
1
1
2

Resources

2016 UESTC Training for Search Algorithm & String