Count Dominant Substrings

Count even-length substrings by index: a substring counts once if at least one character occurs exactly half its length times. If two characters each make up half, it still counts only once.

输入格式

One line with a string. This site sets the length to 1..100000 with lowercase letters only.

输出格式

Output a single integer answer.

样例 1

输入：

aaaaid

输出：

3

样例 2

输入：

abab

输出：

4

样例 3

输入：

aa

输出：

0

样例说明

Example 1: the valid ones are ai, id and aaid, 3 in total; the aa in the source explanation does not satisfy the definition. Example 2: the three substrings of length 2 plus the whole abab, 4 in total. Example 3: in aa, a occurs 2 times rather than half the length, 1, so the answer is 0.