Why Did the Cow Cross the Road II (Bronze)#10533

Why Did the Cow Cross the Road II (Bronze)

1 second
128 megabytes
Easy

The layout of Farmer John's farm is quite peculiar, with a large circular road running around the perimeter of the main field where his cows graze during the day. Every morning, the cows cross this road on their way into the field, and every evening, they cross it again as they leave the field and return to the barn.

As we know, cows are creatures of habit, and each cow crosses the road in the same way every day. Each cow enters the field at a different point from where she exits, and all of these crossing points are distinct from each other. Farmer John owns exactly cows, which he has lazily named through (he is not sure what he will do if he ever acquires a -th cow...), so there are precisely crossing points around the road.

Farmer John records these crossing points by scanning around the circle clockwise and writing down the name of the cow at each crossing point. This produces a string of characters in which each letter of the alphabet appears exactly twice. He does not record which crossing points are entry points and which are exit points.

Looking at his map of crossing points, Farmer John is curious about how many pairs of cows might cross paths during the day. He calls a pair of cows a "crossing pair" if the path cow takes from her entry point to her exit point must cross the path cow takes from her entry point to her exit point. Help Farmer John count the total number of crossing pairs.

Input

One line contains a string of uppercase characters. Each letter of the alphabet appears exactly twice.

Output

Print the total number of crossing pairs.

Examples

In this example, only cows and form a crossing pair.

Example 1

Loading
Loading