The largest block

The Block of a string S at position i is the largest substring S which starts at position i and matches with the prefix S. The length of the block started at position 0 is assumed to be zero.

Find the length of the largest block for the given string S.

Input

The only string of S (|S| ≤ 10^6).

Output

The length of the largest block of string S.

Examples