Cursor Distance

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 = abaab with the cursor on the second character (a[b]aab), then:

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

Let 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 ∑{i = 1}^n ∑{j = 1}^n 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 ∑{i = 1}^n ∑{j = 1}^n dist(i, j).

Examples

Input

abcde

Output

20

Input

abacaba

Output

58

Note

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

inputFormat

Input

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

outputFormat

Output

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

Examples

Input

abcde

Output

20

Input

abacaba

Output

58

Note

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

样例

abacaba

58

</p>