Background

Description

We'll say that a "pair" in a string is two instances of a char separated by a char. So "AxA" the A's make a pair. Pair's can overlap, so "AxAxA" contains 3 pairs -- 2 for A and 1 for x. Recursively compute the number of pairs in the given string.

Format

Input

Output

Samples

axa

1

axax

2

axbx

1

Limitation

1s, 1024KiB for each test case.