Background

Special for beginners, ^_^

Description

求一个串由多少个重复子串构成。

Format

Input

每行包含一个字符串，每个字符串的长度为不超过11M的正整数。最后一组测试数据的下一行是一个句号。

Output

每行输出一个答案，表示该串的最大重复子串数。

Samples

abcd
aaaa
ababab
.

1
4
3

Limitation

1s, 1024KiB for each test case.

Source