题目描述

原题来自：POJ 2406

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

输入格式

按照题目要求输出若干个整数， 每行一个。

输出格式

一行 $n$ 个数，为 $1 \sim n$。

abcd
aaaa
ababab
.

1
4
3

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^7$。