给定一个长度为 $n$ 的由小写英文字母组成的字符串 $S$。我们用 $\text{Suffix}_i$ 表示 $S$ 从第 $i$ 个字符开始的后缀。定义 $w_{i,j}$ 为 $\text{Suffix}_i$ 和 $\text{Suffix}_j$ 的 $LCP$ 长度。$LCP$ 即两个字符串的最长公共前缀。例如，$\text{abca}$ 和 $\text{abd}$ 的 $LCP$ 为 $\text{ab}$。
你需要将 $1$ 到 $n$ 的整数划分为两个非空的互补集合 $T_1, T_2$。我们定义该划分的值为：
$$\sum_{i \in T_1} \sum_{j \in T_2} w_{i,j}$$
请找到一个划分，使得该值最小。
输入格式
输入包含一个长度为 $n$ ($2 \le n \le 10^5$) 的字符串 $S$，占一行，仅由小写英文字母组成。
输出格式
输出一个整数，表示最小的值。
样例
样例输入 1
aa
样例输出 1
1
样例输入 2
ab
样例输出 2
0