Maximize Beautiful Substrings

The string contains only lowercase letters and dots; each dot can be replaced with any lowercase letter. A beautiful substring is a contiguous substring whose characters are all the same. Find the maximum total number of beautiful substrings after the replacements.

The source problem's rules and examples are clear; this site adds the input character set, the length limit, and stdin/stdout.

输入格式

A single line containing the string color (1≤length≤2000), whose characters are only a-z or . (dot).

输出格式

Output the maximum number of beautiful substrings.

样例 1

输入：

.a.bb.

输出：

13

样例 2

输入：

a...b

输出：

11

样例 3

输入：

....

输出：

10