$w$ と $u$ を英小文字からなる文字列とします。$|w|=n$、$|u|=k$ として、すべての $j=1,\ldots,k$ に対し $u[j]=w[i_j]$ を満たす狭義単調増加する整数列 $i_1,\ldots,i_k$ が存在するとき、文字列 $u$ は文字列 $w$ の部分列であるといいます。ここで $v[i]$ は文字列 $v$ の $i$ 番目の文字を表します。$w[i:]$ は接尾辞 $w[i]\cdots w[n]$ を表すものとします。$i>n$ なら、$w[i:]$ は $\lambda$ と表す空文字列です。

空でない文字列 $w$ と正整数 $k$ に対し、$w$ の $k$-集合を、長さが $0,1,\ldots,k$ の $w$ の部分列からなる集合 $Q_k(w)$ と定義します。この定義から、任意の文字列 $w$ に対して、空文字列 $\lambda$ は $Q_k(w)$ に属します。

例えば、$w=aaba$ のとき、$Q_3(aaba)=\{\lambda,a,b,ba,ab,aa,aba,aab,aaa\}$ です。

文字列 $w$ のランクを、$w$ のすべての接尾辞の $t$-集合がすべて異なるような最小の整数 $t$ と定義します。つまり、$w$ のランクは $\min\{t\ge1\mid Q_t(w[i:])\ne Q_t(w[j:]),\ \forall1\le i<j\le n\}$ です。

例えば、$w=aaba$ のとき、2-集合 $Q_2(aba)$ と $Q_2(aaba)$ は等しくなります。一方、$t=3$ のときは次のようになります。

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

したがって、文字列 $w=aaba$ のランクは 3 です。

文字列 $w$ が与えられます。そのランクを出力するプログラムを作成してください。

入力

プログラムは標準入力から読み込んでください。入力は英小文字のみからなる、空でない文字列 $w$ 1 つです。文字列の長さは最大 $3\times10^6$ です。

出力

プログラムは標準出力に書き出してください。ちょうど 1 行を出力してください。その行には、入力文字列 $w$ のランク $t$ を表す正整数を含めてください。

以下は 4 つのテストケースの入力例と出力例です。

入出力例

入力 1

aabbb

出力 1

3

入力 2

abacb

出力 2

2

入力 3

azadzzadaz

出力 3

4

入力 4

a

出力 4

1