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 ∑∑dist(i,j).

Input The only line contains a non-empty string s of at most 105 lowercase English letters.

Output Print a single integer ∑∑dist(i,j).