Niech $w$ i $u$ będą napisami złożonymi z małych liter alfabetu angielskiego. Mówimy, że napis $u$ jest podciągiem napisu $w$, jeśli istnieje ściśle rosnący ciąg liczb całkowitych $i_1,\ldots,i_k$, gdzie $|w|=n$, $|u|=k$ oraz $u[j]=w[i_j]$ dla każdego $j=1,\ldots,k$. Tutaj $v[i]$ oznacza $i$-ty znak napisu $v$. Niech $w[i:]$ oznacza sufiks $w[i]\cdots w[n]$. Jeśli $i>n$, to $w[i:]$ jest pustym napisem, oznaczanym przez $\lambda$.

Dla niepustego napisu $w$ i dodatniej liczby całkowitej $k$ definiujemy $k$-zbiór napisu $w$ jako zbiór $Q_k(w)$ podciągów $w$ o długościach $0,1,\ldots,k$. Z definicji wynika więc, że dla dowolnego napisu $w$ pusty napis $\lambda$ należy do $Q_k(w)$.

Na przykład dla $w=aaba$ mamy $Q_3(aaba)=\{\lambda,a,b,ba,ab,aa,aba,aab,aaa\}$.

Rangę napisu $w$ definiujemy jako najmniejszą liczbę całkowitą $t$, dla której $t$-zbiory wszystkich sufiksów $w$ są parami różne. Innymi słowy, ranga $w$ to $\min\{t\ge1\mid Q_t(w[i:])\ne Q_t(w[j:]),\ \forall1\le i<j\le n\}$.

Na przykład dla $w=aaba$ 2-zbiory $Q_2(aba)$ i $Q_2(aaba)$ są równe. Natomiast dla $t=3$ mamy

$$\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}$$

Zatem ranga napisu $w=aaba$ wynosi 3.

Dla danego napisu $w$ napisz program wypisujący jego rangę.

Wejście

Program ma czytać ze standardowego wejścia. Wejście zawiera jeden niepusty napis $w$, złożony wyłącznie z małych liter alfabetu angielskiego. Jego długość nie przekracza $3\times10^6$.

Wyjście

Program ma pisać na standardowe wyjście. Wypisz dokładnie jeden wiersz zawierający dodatnią liczbę całkowitą oznaczającą rangę $t$ wejściowego napisu $w$.

Poniżej podano przykładowe wejście i wyjście dla czterech przypadków testowych.

Przykład

Wejście 1

aabbb

Wyjście 1

3

Wejście 2

abacb

Wyjście 2

2

Wejście 3

azadzzadaz

Wyjście 3

4

Wejście 4

a

Wyjście 4

1