题目描述

瓜瓜特工接到了一个新任务——保护CB直到毕业。

于是瓜瓜就装作实验室的集训队员潜伏在集训队，同时暗中保护CB的安全，并装弱让CB不要对ACM丧失信心。

某天早上，瓜瓜发现CB不在实验室，便打了个电话。

电话接通了，但是电话那头传来了陌生男人的声音。

“CB现在在我们手上，嘿嘿嘿♂ ……”。电话那头说完这句话就挂断了。

“CB！！！”瓜瓜大喊。

冷静下来的瓜瓜，发现了CB留下的纸条，上面的答案就是CB所在位置（聪明的CB自然不可能白白被抓走

rbq("wobeihuairenzhuazoulewwwkuailaijiuwoguagua")

这个 $\textrm{rbq}(\texttt{str})$ 函数是 CB 之前跟瓜瓜讲过 LSP 库里的一个函数。

这个函数的参数是一个字符串，返回的是 $\texttt{str}$ 中子串的最大循环次数。

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

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

输入格式

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

接下来 $T$ 行，每行包含一个长度小于 $5 \times 10^3$ 的字符串，字符串仅包含大小写字母与数字。

输出格式

每一组输出一个整数，代表 $\texttt{str}$。

样例

2
psdababab2345
avabcdad

3
1

提示

样例解释： $\textrm{rbq}(\texttt{psdababab2345}) = 3$ 因为子串 $\texttt{ababab}$ 有 $\texttt{ab}$ 的循环节，并且循环了 $3$ 次，所以答案为 $3$。

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