J. Jesting Jabberwocky
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
In Sample 1, Alice has to move at least two cards to sort her hand.
The famous card game manufacturer Greatest Cards Production Company (GCPC) has just created the brand new card game Jabberwocky. In this game, everyone gets the same amount of cards – which might be quite a lot – and each card belongs to one of four different suits: hearts, diamonds, clubs, or spades.

As huge card game nerds, Alice and her friends are very hyped about meeting up and trying out the card game everybody seems to talk about these days. Due to a traffic jam, Alice is a bit late to the party and her friends are impatiently waiting for her. They have already distributed all cards and everybody is ready to go, except for Alice. She has just picked up her cards and insists on sorting them by suit first. For that, she repeatedly picks one card from her hand and inserts it somewhere else until her cards are grouped by suit. Her friends are getting increasingly annoyed with Alice and she wants to sort her cards as quickly as possible. How many cards does Alice need to move before they can start playing?

Input

The input consists of:

  • One line with a string $$$s$$$ ($$$1\leq|s|\leq 10^5$$$), representing the suits of Alice's cards as they are initially ordered. The string consists of the characters h, d, c, and s (hearts, diamonds, clubs and spades).
Output

Output a single integer, the minimum number of cards Alice has to move in order to sort the cards by suit.

Examples
Input
hccdhcd
Output
2
Input
cchhdshcdshdcsh
Output
7