Problem K: circulation circulation circulation!

Problem K: circulation circulation circulation!

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 97  Solved: 28
[Submit] [Status] [Web Board] [Creator:]

Description

作为一个防ak题,你点进来就是给我这个"防ak题"面子,下面是送你一道简单字符串题

问有这样一个字符串(由小写字母构成) 它最多可以由多少个相同子串循环得到
如:abababab由4个ab组成
是不是很简单,a掉它吧

Input

第一行输入T(0<T<=10),表示有T个字符串
下面T行,每行输入一个字符串(0<L<=1e7,L是字符串长度)

Output

输出T行,每行一个整数(这个字符串最多由几个相同子串循环得到)

Sample Input Copy

2
abababab
aaa

Sample Output Copy

4
3