题目描述

记 $f(S)$ 为字符串 $S$ 的最小表示，具体地，把 $S$ 中第一次出现的字母替换为 $\texttt{a}$，第二次出现的字母替换为 $\texttt{b}$，等等。

例如，$f(\texttt{AGACC})=\texttt{abacc}$。

给定一个长度为 $n(1\le n\le 10^5)$ 的只包含 $\texttt{A,C,G,T}$ 的字符串，输出其有多少个本质不同的非空子串。定义两个串 $A,B$ 本质不同当且仅当 $f(A)$ 与 $f(B)$ 不同。

输入

一行一个由 $\{\texttt{A,C,G,T}\}$ 组成的非空字符串。

输出

一行一个整数表示答案。

ACGT

4

AAAA

4