G. Kozak Vus and Lines

Kozak Vus recently encountered the following problem:

Given a string $s$, determine the number of substrings that meet the following criteria:

1. The substring must contain at least $3$ characters.

2. All characters in the substring are identical except for one.

For instance, the substrings aab and cccdc meet these criteria, whereas ab, ccc, and aabbaa do not.

A string $x$ is considered a substring of string $y$ if $x$ can be derived by removing zero or more characters from the beginning and zero or more characters from the end of $y$.

Assist Kozak Vus in solving this problem.

Input

The first line contains the string $s$ ($1\le |s|\le 2\cdot 10^5$), composed of lowercase Latin letters.

Output

Output a single integer — the number of substrings that satisfy the specified conditions.

Examples

Scoring

A solution that works correctly for $|s|\le 100$ will earn at least $15$ points.

A solution that works correctly for $|s|\le 5000$ will earn at least $40$ points.