Giải bài trực tuyến

You are given a string and are allowed to perform some operators on this string. In each operator, you can change all characters of a type to another type. The cost of an operator is the number of characters affected. The cost of several operators is the total cost of each individual operator.

For example, the string acaabc will become abaabbif you change all c's to b's. The cost of this operator is 2 since there are 2 c's in the first string.

What is the minimum cost to make the given string a palindrome?

Input

• The original string is given in the first line.

Output

• The minimum cost to make the string a palindrome.

Example

Input:

acaabc


Output:

3

Constraints

• The length of the input string does not exceed 10⁵.
• Each character of the input string is either a letter or a digit.
• In 50% of the test cases, the length of the input string does not exceed 100.