The largest border#1307

The largest border

1 second

128 megabytes

Very easy

A border (verge, brink) of a string $S$ is any proper prefix of the string that is equal to its suffix.

For example, the string $S = abaababaabaab$ S = abaababaabaab has two non-empty borders: $ab$ and $abaab$ .

The string $S = abaabaab$ S = abaabaab also has two such borders — $ab$ and $abaab$ , with the second border being overlapping.

A string of length $n$ consisting of a repeated character (for example, $aaaaaaaa$ or $a^{8}$ a^8) has $n - 1$ n - 1 borders. For $S = a^{8}$ S = a^8, these borders are: $a$ , $aa$ , $aaa$ , $aaaa$ , $aaaaa$ , $aaaaaa$ , $aaaaaaa$ .

The term proper prefix excludes the border that coincides with the entire string.

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

A natural generalization of the border is the longest border — the longest proper prefix of the string that is equal to its suffix.

Input

One string $S (∣ S ∣ \leq 1 0^{6})$ S~(|S| \le 10^{6}).

Output

Print the length of the longest border of the string $S$ .

Examples

Example 1

Loading

S = abaababaabaab

S = abaabaab

a^{8}

n - 1

S = a^{8}

S (∣ S ∣ \leq 1 0^{6})