题目描述

瓜瓜特工接到了一个新任务——保护CB直到毕业。 于是瓜瓜就装作实验室的集训队员潜伏在集训队，同时暗中保护CB的安全，并装弱让CB不要对ACM丧失信心。 某天早上，瓜瓜发现CB不在实验室，便打了个电话。 电话接通了，但是电话那头传来了陌生男人的声音。 “CB现在在我们手上，嘿嘿嘿♂ ……”。电话那头说完这句话就挂断了。 “CB！！！”瓜瓜大喊。 冷静下来的瓜瓜，发现了 CB 留下的纸条，上面的答案就是 CB 所在位置（聪明的 CB 自然不可能白白被抓走）。 rbq("wobeihuairenzhuazoulewwwkuailaijiuwoguagua") 这个rbq(string) 之前跟瓜瓜讲过 LSP 库里的一个函数。

这个函数的参数是一个字符串，返回的是 string中子串的最大循环次数。

CB 为了不让坏人发现，把这个字符串用很多无用的字符填充了起来。但是字符串太长了，瓜瓜根本无法肉眼看出来。

于是瓜瓜找到了你，希望你能写个程序告诉他 CB 所在位置。

输入描述

第一行包含一个整数 $T$，代表总共有 T($1 \leq T \leq 10^3$)组字符串。

接下来 $T$行，每行包含一个长度小于 $5*10^3$的字符串，字符串仅包含大小写字母与数字。数据保证$\sum |string| \leq 5*10^3$

输出描述

每一组输出一个整数，代表rbq(str)

样例输入

2
psdababab2345
avabcdad

样例输出

3
1

说明

rbq(psdababab2345)=3 因为子串 ababab有循环节 ab，并且循环了 3次，所以答案为 3。

rbq(avabcdad)=1, 因为任何一个子串都没有循环次数超过 1的循环节，所以答案为 1。