The Humble Institution of Inversion Techniques has designed a completely new and amazing type of strings called hiitdromes. A string is a hiitdrome if it only uses the letters H, I, and T, and reads the same forwards and backwards. They like hiitdromes so much that they wonder how difficult it is to transform arbitrary words into hiitdromes. On a single operation, one may add, remove, or replace a single character into another anywhere in the string. Given a string of n characters, what is the minimum number of operations it takes to make it a hiitdrome?

Input

The first line of the input contains a single integer, n.

The second line of the input contains the string s.

Output

Output a single integer that is the minimum number of operations required for transforming s into a hiitdrome.

Constraints

• 1 \le n \le 1000

Example

Input:

6
HEITTO

Output:

3

Explanation: One way to make HEITTO into a hiitdrome is to remove E, replace O by I, and add H at the end of the string.