Problem I
Compressible Passwords

Commonly used compression software.

Your boss just got a great idea for a new type of password. Because substrings of larger strings are very compressible, wouldn’t it be easier if all passwords were just substrings of some very large string that would be kept centrally? Then all passwords could be stored as a single number. No time to discuss, this idea is so great that it has to be implemented straight away.

As only one number can be stored per password according to your boss, all of these substrings must have the same length $K$. Suppose the large string is ABBCD. Then if $K = 1$ the available passwords are A, B, B, C and D. This clearly does not work as there are repeated passwords. But if $K = 2$ then the passwords are AB, BB, BC, CD which works great. But as $K$ gets larger there are fewer passwords available, so we want $K$ as small as possible.

What is the smallest $K$ that lets this work for a given string? That is to say, the smallest $K \geq 1$ such that all substrings of length $K$ are unique.

Input

The first and only line contains a single string. This string will contain only printable ASCII characters and no whitespace. It has length at least $1$ and at most $10^5$.

Output

Print the smallest $K$ that lets your boss’s password idea work.

Explanation of samples

In the first sample it does not suffice to take all substrings of length $1$ since we get the substring B twice. But as soon as we take length $2$ it suffices, as we get the substrings AB, BB, BC, CD.

If we look at length $1$ substrings in the second sample we get both A and B several times. Similarly for length $2$ we get AB repeating, among other issues. For $3$ the substring ABB appears twice and for $4$ the substring ABBA appears twice. It’s not until length $5$ where we get all substrings different. We get ABBAA, BBAAB, BAABB, AABBA which are all different.

ABBCD

2

ABBAABBA

5