Alphabet String

Insert the fewest lowercase letters into s so that deleting some letters leaves exactly a through z in order.

Medium5Dynamic programmingStringGreedyBinary searchInterviewNo attempts yetTime limit2sMemory limit512 MB

Description

Examples5

Problem

A string of lowercase letters is alphabetical if you can delete some of its letters so that exactly the letters a through z remain, in that order.

You are given a string $s$ . You may insert lowercase letters at any positions of $s$ to make it alphabetical. Find the minimum number of letters you have to insert.

Input

The input consists of a single test case. The same program may be run several times on different inputs.

The first line contains a string $s$ of lowercase letters. ( $1 \le |s| \le 50$ )

Output

Print one line with the minimum number of letters that must be inserted into $s$ to make it alphabetical.