Let $w$ be a given word — a sequence of $n$ lowercase English letters. For given positions, i.e., natural numbers $a$ and $b$ such that $1 \le a \le b \le n$, we define the substring $w_{a,b}$ as the word obtained by taking all characters in order from the $a$-th position to the $b$-th position in the word $w$. We also define the remainder $o_{a,b}$ as the word obtained when we delete all characters from the $a$-th position to the $b$-th position in the word $w$.
Find the length of the longest substring $w_{a,b}$ such that the remainder $o_{a,b}$ also contains $w_{a,b}$ as a substring.
Input
The first line contains the given word $w$ — a sequence of lowercase English letters.
Output
Print the required maximum possible length.
Subtasks
Let $n$ be the length of the given word.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 16 | $1 \le n \le 400$ |
| 2 | 24 | $401 \le n \le 5\,000$ |
| 3 | 60 | $5001 \le n \le 100\,000$ |
Examples
Input 1
abcxyzabc
Output 1
3
Input 2
bbcdbcbbcbadadda
Output 2
5
Note
Explanation of the second example: bbcdbcbbcbadadda $\to$ bbcdbcbadda. In this case, the substring bbcdb (length 5) is removed, and the remaining word bbcdbcbadda contains bbcdb as a substring.