题目描述

给定若干个长度 $\le 10^6$ 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。 例如：字符串 ababab 最多由 $3$ 个 "ab" 连接而成。

输入格式

输入若干行，每行一个字符串。 特别地，字符串可能为空，即一个半角句号 .，表示输入结束。

输出格式

对于每个输入的字符串，输出一个整数，表示该字符串最多能由多少个相同子串重复组成。

样例数据

abcd
aaaa
ababab
.

1
4
3

数据范围与提示

• 字符串长度 $\le 10^6$
• 建议使用 KMP 前缀函数（π 表）优化求解。