Description

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

Input format

输入文件由若干行组成。每行表示一个字符串S（1<strlen（s）<=1,000,000,000）。输入文件的最后一行以"."结束。

Sample 1

Input

abcd
aaaa
ababab
.

Output

1
4
3

Limitation

1s, 64MiB for each test case.

Source

poj2406