Stones on the Table

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

There are n colored stones in a row, each represented by R, G or B. Remove as few stones as possible so that any two neighboring remaining stones have different colors while preserving order.

Input

The first line is n; the second line contains exactly n consecutive characters from R, G, and B.

Output

Print the minimum number of stones to remove.

Subtasks

• Subtask 1 (20%): $1\le n\le5$.
• Subtask 2 (30%): $1\le n\le20$.
• Subtask 3 (50%): $1\le n\le50$.

Examples

Example 1

Input

3
RRG

Output

1

Explanation

The first two R stones form one same-colored run; remove one stone.

Example 2

Input

5
RRRRR

Output

4

Explanation

Five consecutive R stones require removing four of them.