• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

یک نوار رنگی داریم که به صورت یک سطر افقی شامل $n$ خانه است. هر خانه با یکی از $k$ رنگ موجود رنگ شده است. می‌خواهیم رنگ حداقل تعداد خانه‌ی لازم را تغییر دهیم به صورتی که در نهایت هیچ دو خانه‌ی مجاوری رنگ یکسان نداشته باشند. برای تغییر رنگ خانه‌ها، از هر رنگ دلخواه بین ١ تا $k$ می‌توانیم استفاده کنیم.

ورودی

خط اول ورودی شامل دو عدد صحیح $n$ و $k$ است. خط دوم شامل $n$ حرف بزرگ انگلیسی است. حرف A به معنای رنگ اول، حرف B به معنای رنگ دوم، و به همین ترتیب تا حرف Z به معنای رنگ ٢۶ام است. تنها $k$ حرف اول انگلیسی می‌توانند ظاهر شوند. هر حرف نماینده‌ی رنگ خانه متناظرش در نوار است.

$$1 \leq n \leq 5 \times 10^5$$ $$2 \leq k \leq 26$$

خروجی

در تنها خط خروجی، حداقل تعداد خانه‌ای که لازم است رنگ آن‌ها عوض شود را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

6 3
ABBACC

خروجی نمونه ۱

2

در مثال بالا با تغییر دادن رنگ خانه‌ها از ABBACC به ACBABC به خواسته ی مورد نظر می‌رسیم.

ورودی نمونه ۲

3 2
BBA

خروجی نمونه ۲

1

در مثال بالا کافی است رنگ خانه‌ی اول را به A تغییر دهیم.