You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Original source: POJ 2406

Given several strings with lengths $\le 10^6$, determine the maximum number of identical substrings each string can be formed by concatenating. For example, ababab can be formed by concatenating $3$ ab substrings.

Input Format

Input consists of several lines, each containing a string. Specifically, the string may be . (a single period), which indicates the end of input.

Sample 1

abcd
aaaa
ababab
.

1
4
3

Constraints and Hints

String length $\le 10^6$.