Se da una palabra $w$: una secuencia de $n$ letras minúsculas del alfabeto inglés. Para unas posiciones dadas, es decir, números naturales $a$ y $b$ tales que $1\le a\le b\le n$, definimos la subpalabra $w_{a,b}$ como la palabra que obtenemos tomando todos los caracteres, en orden, desde la posición $a$ hasta la posición $b$ de la palabra $w$. También definimos el resto $o_{a,b}$ como la palabra que obtenemos al borrar de la palabra $w$ todos los caracteres desde la posición $a$ hasta la posición $b$.
Encuentra la longitud de la subpalabra $w_{a,b}$ más larga tal que el resto $o_{a,b}$ también contenga $w_{a,b}$ como subpalabra.
Entrada
La primera línea contiene la palabra dada $w$: una secuencia de letras minúsculas del alfabeto inglés.
Salida
Imprime la longitud máxima posible que se pide.
Subtareas
Sea $n$ la longitud de la palabra dada.
| Subtarea | Puntos | Restricciones |
|---|---|---|
| $1$ | $16$ | $1\le n\le 400$ |
| $2$ | $24$ | $401\le n\le 5\,000$ |
| $3$ | $60$ | $5001\le n\le 100\,000$ |
Ejemplos
Entrada 1
abcxyzabc
Salida 1
3
Entrada 2
bbcdbcbbcbadadda
Salida 2
5
Nota
Explicación del segundo ejemplo: $\texttt{bbcdbcb}\underline{\texttt{bcbad}}\texttt{adda}\to\texttt{bbcd}\underline{\texttt{bcbad}}\texttt{da}$.