There is a string $s$ of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter $c$ and a direction (left or right). The cursor is then moved to the closest occurence of $c$ in the chosen direction. If there is no letter $c$ in that direction, the cursor stays in place. For example, if $s = \mathtt{abaab}$ with the cursor on the second character ($\mathtt{a[b]aab}$), then:

• moving to the closest letter $\mathtt{a}$ to the left places the cursor on the first character ($\mathtt{[a]baab}$);
• moving to the closest letter $\mathtt{a}$ to the right places the cursor the third character ($\mathtt{ab[a]ab}$);
• moving to the closest letter $\mathtt{b}$ to the right places the cursor on the fifth character ($\mathtt{abaa[b]}$);
• any other operation leaves the cursor in place.

Let $\mathrm{dist}(i, j)$ be the smallest number of operations needed to move the cursor from the $i$-th character to the $j$-th character. Compute $\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$.

Input

The only line contains a non-empty string $s$ of at most $10^5$ lowercase English letters.

Output

Print a single integer $\displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j)$.

Note

In the first sample case, $\mathrm{dist}(i, j) = 0$ for any pair $i = j$, and $1$ for all other pairs.