You are given a string s with length n and your task is to find the length of the maximum repeating prefix. A repeating prefix of s is a substring s[a\ldots b], 1 \le a \le b < n such that s[a\ldots b] = s[0\ldots b-a], that is s[a\ldots b] is equal to the prefix of s. The maximum repeating prefix is the longest of repeating prefixes.

Input

The first and only line of input contains string s with n characters between a-z. All letters are small case.

Output

Output the length of the maximum repeating prefix.

Limits

• 1 \le n \le 10^6

Example

Input:

abcdabcdabcd

Output:

8

Explanation:
The repeating prefix is abcdabcdabcd