题目描述

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

输入格式

每行一个长度小于等于1000000的字符串
最后一行由‘.’结束

输出格式

按行输出每个字符串最多由多少个相同的子串重复连接而成。

样例数据

input

abcd
aaaa
ababab
.

output

1
4
3