Facets of the string#8230

Facets of the string

1 second
64 megabytes
Very easy

A border of a string is defined as a proper prefix that is also equal to a suffix (the entire string is not considered a proper prefix). For example, the string T = abaababaabaab has two non-empty borders: ab and abaab. Similarly, the string T = abaabaab also has two non-empty borders: ab and abaab, with the second border overlapping its prefix. A string consisting of identical characters has n-1 borders; for example, T = aaaaaaaa has the borders: a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaaaa. The length of a border is the number of characters it contains. Among all borders, the largest border is the longest proper prefix that is also a suffix.

Your task is to find the length of the largest border of the given string .

Input

The input contains a single line with the string (1 \leq |T| \leq 10^5), consisting only of Latin letters.

Output

Output a single integer: the length of the largest border.

Examples

Example 1

Loading
Loading