The largest block#1310

The largest block

1 second

64 megabytes

Very easy

The block of a string $S$ at position $i$ is the longest substring of $S$ that starts at position $i$ and matches the prefix of $S$ . The length of the block at position $0$ is considered to be zero.

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

Input

The only input line contains the string $S$ ( $∣ S ∣ \leq 1 0^{6}$ |S| \leq 10^6).

Output

Print the length of the largest block of the string $S$ .

Examples

Example 1

Loading

∣ S ∣ \leq 1 0^{6}