重复字符串

题目描述:

给定两个字符串a和b，我们可以定义一些操作：a*b为将字符串a和字符串b连接起来，比如a= "aoe"，b= "jkw"，那么a*b= "aoejkw"。进一步，我们可以有指数操作，a^0= ""， a^1=a， a^2=a*a， a^n=a*(a^(n-1))=a*a*…*a (n个a)

现在给你一个字符串，你可以将它看成是a^n的形式，比如字符串"abababab"，可以认为是"abab"^2， 也可以是"abababab"^1，还可以是"ab"^4。

现在问题是，给定的字符串，我们想让它变成a^n中的n达到最大，那么这个n最大是多少？例如："abababab"最大的n是4。

输入格式:

第一行，一个整数m，表示有m个字符串。

接下来m行每行输入一个只含小写字母的字符串。

输出格式:

输出m行，对于每行输出相应字符串的最大n。

样例输入:

3
abcde
aaaaaa
abababab

样例输出:

1
6
4

提示:

【数据规模】

30%的数据：字符串的长度≤1000；

100%的数据：字符串的长度≤1000000， m≤10，字符串内只含小写字母。

时间限制: 1000ms
空间限制: 256MB

---