Line block

In a string T, the block at position i is defined as the longest substring starting at position i that matches the prefix of T. Note that the length of the block at position 0 is zero. Your task is to determine the length of the largest block in the given string T.

Input

The input consists of a single line containing the string T (1 ≤ length(T) ≤ 10^5), composed entirely of Latin letters.

Output

Print a single integer representing the length of the largest block.

Examples