Description

设 $w$ 和 $u$ 是由英文小写字母组成的字符串。如果存在一个严格递增的整数序列 $i_1, \dots, i_k$，其中 $|w| = n$，$|u| = k$，且对于所有 $j = 1, \dots, k$ 有 $u[j] = w[i_j]$，则称字符串 $u$ 是字符串 $w$ 的一个子序列。这里 $v[i]$ 表示字符串 $v$ 的第 $i$ 个字符。令 $w[i:]$ 表示后缀 $w[i] \cdots w[n]$。如果 $i > n$，则 $w[i:]$ 为空字符串，记为 $\lambda$。

给定一个非空字符串 $w$ 和一个正整数 $k$，我们定义 $w$ 的 $k$ 集合 为集合 $Q_k(w)$，它包含 $w$ 中所有长度为 $0, 1, \dots, k$ 的子序列。这意味着，根据定义，对于任何字符串 $w$，空字符串 $\lambda$ 都属于 $Q_k(w)$。

例如，当 $w = \text{aaba}$ 时，有 $Q_3(\text{aaba}) = \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}, \text{aab}, \text{aaa}\}$。

对于一个字符串 $w$，我们定义 $w$ 的 秩 为最小整数 $t$，使得 $w$ 的所有后缀的 $t$ 集合互不相同。换句话说，$w$ 的秩是 $\min\{t \geq 1 \mid Q_t(w[i:]) \neq Q_t(w[j:]), \forall 1 \leq i < j \leq n\}$。

例如，当 $w = \text{aaba}$ 时，2 集合 $Q_2(\text{aba})$ 和 $Q_2(\text{aaba})$ 是相等的。另一方面，对于 $t = 3$，我们有

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

因此，字符串 $w = \text{aaba}$ 的秩为 $3$。

给定一个字符串 $w$，请编写一个程序输出其秩。

Input Format

你的程序需要从标准输入读取数据。输入包含一个非空字符串 $w$，该字符串仅由英文小写字母组成。字符串的长度不超过 $3 \times 10^6$。

Output Format

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含一个正整数，表示输入字符串 $w$ 的秩 $t$。

aabbb

3

abacb

2

azadzzadaz

4

a

1