Problem D
Self-Similar Strings

An object is sometimes called ‘self-similar’ if there are parts of it that are repeated in other places within the same object. Fractals are self-similar mathematical objects, where the similarities occur at different sizes.

Here, we’ll consider ‘self-similar strings.’ We’ll say that a string $s$ is self-similar to degree $d$ if all $d$-length substrings of $s$ occur in at least one other location in $s$. For example, the string ‘babbabb’ is self-similar to degree 0, degree 1, and degree 2. It is not self-similar to any greater degree. It should be clear that $d \leq |s|-1$.

Write a program which determines the largest degree of self-similarity for given strings.

Input

Input is a list of up to 10000 strings, one per line. Each string is made of up to 80 lower-case alphabet characters (a-z). Input ends at the end of file.

Output

For each string, print the largest degree to which the string is self-similar.

abcdefg
aaaaaa
bababab
aaabbbccc

0
5
4
1