Dane jest słowo $w$ — ciąg $n$ małych liter alfabetu angielskiego. Dla danych pozycji, czyli liczb naturalnych $a$ i $b$ spełniających $1 \le a \le b \le n$, definiujemy podsłowo $w_{a,b}$ jako słowo otrzymane przez wzięcie kolejno wszystkich znaków słowa $w$ od pozycji $a$ do pozycji $b$. Definiujemy również resztę $o_{a,b}$ jako słowo otrzymane po usunięciu ze słowa $w$ wszystkich znaków od pozycji $a$ do pozycji $b$.
Znajdź długość najdłuższego podsłowa $w_{a,b}$, dla którego reszta $o_{a,b}$ również zawiera $w_{a,b}$ jako podsłowo.
Wejście
Pierwszy wiersz zawiera dane słowo $w$ — ciąg małych liter alfabetu angielskiego.
Wyjście
Wypisz szukaną największą możliwą długość.
Podzadania
Niech $n$ oznacza długość danego słowa.
| Podzadanie | Liczba punktów | Ograniczenia |
|---|---|---|
| 1 | 16 | $1 \le n \le 400$ |
| 2 | 24 | $401 \le n \le 5\,000$ |
| 3 | 60 | $5001 \le n \le 100\,000$ |
Przykład
Wejście 1
abcxyzabc
Wyjście 1
3
Wejście 2
bbcdbcbbcbadadda
Wyjście 2
5
Uwagi
Wyjaśnienie drugiego przykładu: bbcdbcbbcbadadda $\to$ bbcdbcbadda