The biggest border of the substring#1308

The biggest border of the substring

1 second

64 megabytes

Very easy

The border (also called verge or brink) $b r$ of a string $S$ is any proper prefix of the string that is equal to a suffix of $S$ .

For example, the string $S = abaababaabaab$ S = \text{abaababaabaab} has two (non-empty) borders: $ab$ and $abaab$ . The string $S = abaabaab$ S = \text{abaabaab} also has two borders: $ab$ and $abaab$ , but the second border is overlapping. A string of length $n$ consisting of a repeated character, such as $aaaaaaaa$ (or $a^{8}$ a^8), has $n - 1$ n-1 borders. For $S = a^{8}$ S = a^8, its borders are: $a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa$ \text{a}, \text{aa}, \text{aaa}, \text{aaaa}, \text{aaaaa}, \text{aaaaaa}, \text{aaaaaaa}.

The notion of a "proper prefix" excludes the border that is equal to the entire string itself.

The length of a border is the number of characters it contains.

Let us generalize the problem. Suppose you want to compute the values of the largest borders for all prefixes $S [1.. i]$ for $i = 1.. n$ i = 1..n, and store them in the array $b r [1.. n]$ .

Find the maximum value of the border in the array $b r$ for all prefixes of $S$ .

Input

A string $S$ is given ( $∣ S ∣ \leq 1 0^{6}$ |S| \leq 10^6).

Output

Print one number: the answer to the problem.

Examples

Example 1

Loading

S = abaababaabaab

S = abaabaab

a^{8}

n - 1

S = a^{8}

a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa

i = 1.. n

∣ S ∣ \leq 1 0^{6}