P96535

Power Strings

题目描述

给定若干个长度小于等于1000000的字符串，询问每个字符串最多由多少个相同的子串重复连接而成。如ababab，最多由3个ab连接而成

输入

 

输出

 

样例

样例 1

输入

abcd

aaaa

ababab

输出

1

4

3

来源

一本通