The Bajtocki Lotek company specializes in conducting number games and cash lotteries, among which the most popular is a lottery called Letter Game. Bajtazar has also decided to try his luck in the game.

A Letter Game coupon contains $n$ positions. In each of them, one of three letters can be marked: A, B, or C. The figure below shows an example of a filled-out coupon for $n = 10$:

The drawing of winners is conducted using a lottery machine containing $3n$ metal balls of three types: $n$ balls with the letter A, $n$ with the letter B, and $n$ with the letter C. In the upper part of the machine, $n$ holes with a diameter smaller than the diameter of a ball are evenly distributed. At a certain moment during the draw, a pneumatic mechanism is activated, causing one ball to be sucked into each hole. By listing the letters on the drawn balls in order, a sequence of $n$ letters is obtained, which constitutes the result of the draw. The lucky owners of coupons on which exactly this sequence of letters is marked win the grand prize - one million bajtalars to be shared. The figure below shows a draw result for which the above coupon would win the grand prize.

Bajtazar purchased a coupon and marked $n$ letters on it. However, before he could submit his coupon at the collection point, a leak appeared in the media that the draw in the Letter Game is not entirely fair. It was discovered that balls of the same type—that is, with the same letter—repel each other and will never be positioned at adjacent holes during the draw (e.g., the arrangement of balls shown in the figure above would not be possible).

Upon learning this, Bajtazar decided to change the sequence of $n$ letters he indicated so that no two consecutive letters in the sequence are the same. To avoid tempting fate, he would like to change as few letters as possible in his sequence. Help Bajtazar determine how many letters he must change.

Input

The first line of input contains a single integer $n$ ($2 \le n \le 500\,000$). The second line contains a sequence consisting of $n$ characters A, B, and/or C. The sequence contains at least one pair of adjacent identical letters.

Output

The first and only line of output should contain a single positive integer - the minimum number of letters in the sequence that must be changed so that no two identical letters appear next to each other.

Examples

Input 1

10
BAACBBAAAC

Output 1

3