Sean $w$ y $u$ cadenas formadas por letras minúsculas inglesas. Decimos que una cadena $u$ es subsecuencia de una cadena $w$ si existe una secuencia estrictamente creciente de enteros $i_1,\ldots,i_k$, donde $|w|=n$, $|u|=k$ y $u[j]=w[i_j]$ para todo $j=1,\ldots,k$. Aquí, $v[i]$ denota el carácter $i$-ésimo de la cadena $v$. Sea $w[i:]$ el sufijo $w[i]\cdots w[n]$. Si $i>n$, entonces $w[i:]$ es la cadena vacía, denotada por $\lambda$.

Dada una cadena no vacía $w$ y un entero positivo $k$, definimos el $k$-conjunto de $w$ como el conjunto $Q_k(w)$ de subsecuencias de $w$ cuyas longitudes son $0,1,\ldots,k$. Esto implica que, para cualquier cadena $w$, la cadena vacía $\lambda$ pertenece a $Q_k(w)$ por definición.

Por ejemplo, cuando $w=aaba$, tenemos $Q_3(aaba)=\{\lambda,a,b,ba,ab,aa,aba,aab,aaa\}$.

Para una cadena $w$, definimos su rango como el mínimo entero $t$ tal que los $t$-conjuntos de todos los sufijos de $w$ sean distintos entre sí. En otras palabras, el rango de $w$ es $\min\{t\ge1\mid Q_t(w[i:])\ne Q_t(w[j:]),\ \forall1\le i<j\le n\}$.

Por ejemplo, cuando $w=aaba$, los 2-conjuntos $Q_2(aba)$ y $Q_2(aaba)$ son iguales. Por otro lado, para $t=3$ tenemos

$$\begin{aligned}Q_3(\lambda)&=\{\lambda\},\\Q_3(a)&=\{\lambda,a\},\\Q_3(ba)&=\{\lambda,a,b,ba\},\\Q_3(aba)&=\{\lambda,a,b,ba,ab,aa,aba\},\\Q_3(aaba)&=\{\lambda,a,b,ba,ab,aa,aba,aab,aaa\}.\end{aligned}$$

Por tanto, el rango de la cadena $w=aaba$ es 3.

Dada una cadena $w$, escribe un programa que produzca su rango.

Entrada

Tu programa debe leer de la entrada estándar. La entrada consta de una única cadena no vacía $w$, formada exclusivamente por letras minúsculas inglesas. La longitud de la cadena es como máximo $3\times10^6$.

Salida

Tu programa debe escribir en la salida estándar. Escribe exactamente una línea que contenga un entero positivo que represente el rango $t$ de la cadena de entrada $w$.

A continuación se muestran entradas y salidas de ejemplo para cuatro casos de prueba.

Ejemplos

Entrada 1

aabbb

Salida 1

3

Entrada 2

abacb

Salida 2

2

Entrada 3

azadzzadaz

Salida 3

4

Entrada 4

a

Salida 4

1