$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$입니다. 문자열의 길이는 최대 $3\times10^6$입니다.

출력

프로그램은 표준 출력에 출력해야 합니다. 정확히 한 줄을 출력하세요. 그 줄에는 입력 문자열 $w$의 랭크 $t$를 나타내는 양의 정수가 들어 있어야 합니다.

다음은 네 테스트 케이스의 예제 입력과 출력입니다.

예제

입력 1

aabbb

출력 1

3

입력 2

abacb

출력 2

2

입력 3

azadzzadaz

출력 3

4

입력 4

a

출력 4

1