String Rank

Let $w$ and $u$ be strings of lowercase English letters. A string $u$ is a subsequence of $w$ if there is a strictly increasing sequence of integers $i_1, \cdots, i_k$ with $|w| = n$, $|u| = k$, and $u[j] = w[i_j]$ for all $j = 1, \dots, k$. Here, $v[i]$ is the $i$-th character of the string $v$. Let $w[i:]$ denote the suffix $w[i] \cdots w[n]$. If $i > n$, then $w[i:]$ is the empty string, denoted $\lambda$.

Given a nonempty string $w$ and a positive integer $k$, the $k$-set of $w$ is the set $Q_k(w)$ of subsequences of $w$ whose lengths are $0, 1, \cdots, k$. By this definition, the empty string $\lambda$ is always in $Q_k(w)$.

For example, when $w$ is aaba, $Q_3(\text{aaba}) = \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}, \text{aab}, \text{aaa}\}$.

The rank of $w$ is the minimum integer $t$ such that the $t$-sets of all suffixes of $w$ are pairwise different. Formally, the rank is $\min\{t \ge 1 \mid Q_t(w[i:]) \ne Q_t(w[j:]) \text{ for all } 1 \le i < j \le n\}$.

For instance, when $w$ is aaba, the 2-sets $Q_2(\text{aba})$ and $Q_2(\text{aaba})$ are equal. For $t = 3$, the suffix sets are $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}\}$, and $Q_3(\text{aaba}) = \{\lambda, \text{a}, \text{b}, \text{ba}, \text{ab}, \text{aa}, \text{aba}, \text{aab}, \text{aaa}\}$. All five are different, so the rank of aaba is 3.

The input consists of a single nonempty string $w$ made only of lowercase English letters. The length of $w$ is at most $3 \times 10^6$.

Print exactly one line containing a positive integer, the rank $t$ of $w$.