Description

对于一个字符串而言，假设有某一个字母只出现过一次，那么我们就称它为“坏子串”。 例如 "abb" ， "bcdde" 就是坏子串，而 "aa" ， "abcacb" 不是坏字符串。

给一个字符串，请问有多少个子串是坏子串。

Input Format

输入一个仅由小写字母组成的字符串。

Output Format

输出一个整数表示答案。

abba

8

Hint

样例一说明： "a" 、"ab" 、"abb" 、"b" 、"bba" 、"b" 、"ba" 、"a"共有8个坏子串。

数据范围 对于 1 − 4 测试点，保证字符串长度不超过 200。 对于 5 − 8 测试点，保证字符串长度不超过 2000。 对于 9 − 10 测试点，保证字符串长度不超过 10^5 且字符种类数不超过 2。 对于 11 − 12 测试点，保证字符串长度不超过 10^5 。 对于 13 − 14 测试点，保证字符串的字符种类不超过 2。 对于 15 − 20 测试点，保证字符串长度不超过 5 × 10^6 。