子串最大循环次数

题目描述

对一个字符串，若其中一个子串可以由某个更短的串（循环节）重复 $k$ 次得到（$k\ge 1$），则称该子串的循环次数为 $k$。定义整个字符串的循环次数为其所有子串循环次数的最大值。

例如，字符串 psdababab2345 的子串 ababab 由 ab 重复 $3$ 次得到，故其循环次数为 $3$。

给定 $T$ 个字符串，请分别求出它们的循环次数。

输入格式

第一行一个整数 $T$（$1\le T\le 10^3$），表示字符串个数。

接下来 $T$ 行，每行一个字符串，仅包含大小写字母和数字，单个字符串长度小于 $5\times 10^3$，且保证 $\sum |string|\le 5\times 10^3$。

输出格式

每组输出一行一个整数，表示该字符串的循环次数。

样例输入

2
psdababab2345
avabcdad

样例输出

3
1

样例解释

psdababab2345 的子串 ababab 以 ab 为循环节重复了 $3$ 次，故答案为 $3$。

avabcdad 中不存在循环次数大于 $1$ 的子串，故答案为 $1$。