Set Total Palindrome Transformation Cost

A string that can be rearranged into a palindrome is called palindrome-like. For any substring, characters may be changed; find the minimum number of changes needed to make it palindrome-like, and output the sum of these costs over all substrings. Rearrangement is allowed here, as the statement defines.

See below for this site's input format and constraints.

输入格式

A single line containing a string s of lowercase English letters only, 1≤|s|≤100000.

输出格式

Output the total palindrome-like change cost over all substrings.

样例 1

输入：

abca

输出：

6

样例 2

输入：

aabb

输出：

1

样例 3

输入：

abc

输出：

3