Background

Special for beginners, ^_^

Description

众所周知，支付宝密码比较重要，如果只诶设置成简单密码容易破解，设置复杂了记不住。小明决定采用姓名加数字的方式。其中的数字部分是一个字符串子串循环次数的最大值。

Format

Input

第一行包含一个整数 T，代表总共有 T组字符串。 接下来T行，每行包含一个字符串，字符串仅包含大小写字母与数字。 每个测试点的字符串长度总和不超过3MB。

Output

每一组输出一个整数，代表密码的数字部分，

Samples

3
123bcbcbc345
bc123bcbc345
abcdefg

3
2
1

Limitation

1s, 1024KiB for each test case.

Hint

第一个字符串存在循环节bcbcbc，循环了3次，所以输出3。 第二个字符串bc出现了3次，但是子串必须只有循环节，所以输出2。 第三个字符串不存在循环节。