设 $w$ 和 $u$ 为由小写英文字母组成的字符串。如果存在一个严格递增的整数序列 $i_1, \dots, i_k$，使得 $|w| = n, |u| = k$ 且对于所有 $j = 1, \dots, k$ 都有 $w[i_j] = u[j]$，则称字符串 $u$ 是字符串 $w$ 的子序列。此处，$v[i]$ 表示字符串 $v$ 的第 $i$ 个字符。设 $w[i:]$ 表示后缀 $w[i] \dots 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 = aaba$ 时，$Q_3(aaba) = \{\lambda, a, b, aa, ab, ba, aaa, aab, aba\}$。

对于字符串 $w$，我们定义 $w$ 的秩（rank）为满足“$w$ 的所有后缀的 $t$-集互不相同”这一条件的最小整数 $t$。换句话说，$w$ 的秩为 $\min\{t \ge 1 \mid Q_t(w[i:]) \neq Q_t(w[j:]), \forall 1 \le i < j \le n\}$。

例如，当 $w = aba$ 时，$Q_2(aba)$ 和 $Q_2(aaba)$ 相等。另一方面，对于 $t = 3$，我们有：

$Q_3(\lambda) = \{\lambda\}$ $Q_3(a) = \{\lambda, a\}$ $Q_3(ba) = \{\lambda, a, b, ba\}$ $Q_3(aba) = \{\lambda, a, b, aa, ab, ba, aba\}$ $Q_3(aaba) = \{\lambda, a, b, aa, ab, ba, aaa, aab, aba\}$

因此，字符串 $w = aaba$ 的秩为 3。

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

输入格式

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

输出格式

程序向标准输出写入数据。仅打印一行，包含一个正整数，表示输入字符串 $w$ 的秩 $t$。

样例

输入 1

aabbb

输出 1

3

输入 2

abacb

输出 2

2

输入 3

azadzzadaz

输出 3

4

输入 4

a

输出 4

1