eolymp
bolt
Try our new interface for solving problems
Problems

The largest border

The largest border

Time limit 1 second
Memory limit 128 MiB

The border (verge, brink) br of the string S is any proper prefix of this string that is equal to the suffix of S.

A string S = abaababaabaab has two borders (not empty) - ab and abaab. A string S = abaabaab also has two borders - ab and abaab, but the second one is overlapping. A string of length n, formed with a repeating character, like aaaaaaaa (or a^8), has n - 1 borders. For the string S = a^8 the borders are: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa.

The concept of "proper prefix" eliminates the border equals to the string.

The length of the border is the number of characters in it.

The common generalization of the concept "border" is the concept of "biggest border" - the largest (by number of characters) own prefix equal to its suffix.

Input data

Given a string S (|S| ≤ 10^6).

Output data

Print the length of the longest border.

Examples

Input example #1
abaabaab
Output example #1
5