Cho một xâu kí tự \(S\) chỉ gồm các kí tự thuộc tập \(\text{T,R,M}\). Ta được phép thực hiện thao tác sau một số lần (có thể không thực hiện lần nào): Chọn hai vị trí phân biệt \(x,y\) (\(1\le x,y\le |S|\)), rồi hoán đổi hai kí tự ở hai vị trí này cho nhau.
Một xâu được gọi là hợp lệ nếu các kí tự giống nhau luôn nằm liền tiếp nhau. Nói cách khác, mỗi loại kí tự xuất hiện trong nhiều nhất một đoạn liên tục duy nhất trên xâu.
Yêu cầu: Tính số thao tác hoán đổi ít nhất cần thực hiện để biến xâu \(S\) thành một xâu hợp lệ.

Input

Từ tập tin PHANLOAI.INP gồm:

• Dòng đầu tiên chứa \(n\) - chứa độ dài xâu kí tự (\(1\le n\le 10^5\))
• Dòng thứ hai chứa xâu kí tự \(S\) chỉ gồm các kí tự thuộc tập \(\text{T,R,M}\).

Output

• Ghi ra tập tin PHANLOAI.OUT một số nguyên duy nhất là số thao tác hoán đổi ít nhất cần thực hiện.

Example

6
TRTTMM

1

4
TTRR

0

Scoring

• Subtask \(1\) (\(40\%\)): Chỉ có ký tự T và R, \(n\le 1000\).
• Subtask \(2\) (\(30\%\)): Chỉ có ký tự T và R, \(n\le 10^5\)
• Subtask \(3\) (\(30\%\)): Không có ràng buộc thêm.