Vũ Đình Hưng là một chiến thần , thiên tài của thiên hà. Một hôm đang đi du ngoạn vũ trụ thì không may tàu của Hưng đâm vào thiên thạch làm thiên thạch nứt ra tạo đúng thành hình cái móc , móc chặt kéo thuyền của Hưng xuống 1 hành tinh lạ trong khi Hưng đang ngủ say. Hành tinh này có tên là SaiYan. Cũng vì quá chán khi đứng đầu thiên hạ. Hưng quyết định lượn 1 vòng quanh đây để thăm thú kỳ quan. Với con siêu xe Bugatti La Voiture Noire của thời cụ cố Hưng để lại chở Nguyễn Nhật Minh (người bạn anh quen qua đường) cùng máy dò sự sống, nhanh chóng Hưng đã phát hiện ra 1 ngôi làng cách đó không xa . Đến ngôi làng , Hưng phát hiện ra ngôi làng rất trù phú với công nghệ phát triển và điều đặc biệt là rất nhiều những cô gái xinh đẹp . Là một người độc thân lâu năm (vì không có cô gái nào xứng tầm =))), Hưng quyết định thôn tính ngôi làng và biến nó thành của riêng mình. Nhưng thật không may, kế hoạch của Hưng đã bị phát hiện bởi Nguyễn Diên Thiện Nhân - một người dân wibu có tiếng trong làng . Và để ngăn chặn kế hoạch đó , Nhân đã đến gặp Hưng để ngăn cản. Nhân muốn có 1 trận đấu cào cào để dành lại ngôi làng thân yêu. Vốn là một chiến thần thực thụ và là 1 người hiếu chiến, Hưng không chút do dự chấp nhận trận đấu của Nhân còn hứa sẽ tặng Nhân 1 điều ước nếu Nhân thắng . Thoáng chốc đã đến ngày trận đấu diễn ra . Nhân mang đến 1 túi cào cào khủng bố với những trang bị huyền thoại đầy mình . Nhưng ko ăn thua với Hưng khi anh đã chuẩn bị được cũng 1 túi cào cào với năng lực vượt trội so với Nhân . Đánh nửa trận thì Nhân cảm thấy không ổn khi liên tục thua , nên Nhân xin Hưng tái đấu vào ngày mai.Vì tình yêu với Ngôi làng thân thương , Nhân đã đến nhờ sự trợ giúp của một người mà Hưng không ngờ tới - Phù Thuỷ Vương Viết Lượng.Nhân đã dựa vào khát khao chạm đến được mặt trăng của Vương Viết lượng làm 1 giao kèo với ông nếu ông giúp Nhân thắng ông sẽ được đến Mặt Trăng mà ông hằng mong nhớ … Vương Viết Lượng đồng ý ngay lập tức vì ông không thể cưỡng lại giây phút được đến bên trăng . Và thế là với sự giúp đỡ của Vương Viết Lượng , Nhân đã chiến thắng Hưng một cách sát sao . Nhưng không hiểu sao lúc chuẩn bị thực hiện điều ước cho Nhân thì đám cào cào của Hưng lại dính chặt lại với nhau và tên mỗi con cào cào dính lại tạo thành một xâu S (S chưa chắc đã là xâu đối xứng vì các con cào cào có thể bị luồn vào nhau). Vốn để thực hiện điều ước , Nhân và Lượng không còn cách nào khác đành phải đi tìm lại cào cào cho Hưng. Vốn là một người sành điệu những con cào cào của Hưng dược đặt tên bằng một xâu đối xứng . Nhân và Lượng biết vậy cảm thấy việc tìm cào cào khá bất khả thi nên quyết định dùng phép thuật của mình.

Được biết phép thuật của anh có thể cho phép biến 1 kí tự trong xâu thành 1 kí tự bất kì . Biết rằng trong túi cào cào của Hưng có \(K\) con cào cào và sau khi dính lại tạo thành một xâu \(S\) độ dài \(N\). Hãy giúp Hưng tìm lại những chú cào cào này rồi in ra số lần thực hiện phép thuật ít nhất để có thể tìm được chúng

Lưu ý: Vì đây là cào cào của Hưng nên chúng sẽ luôn thiên biến vạn hoá, miễn là xâu đối xứng thì chúng đều là cào cào của Hưng và tên của cào cào phải là 1 xâu con liên tiếp trong s

Dữ liệu

• Dòng thứ nhất gồm 2 số \(N\) và \(K\) lần lượt là độ dài xâu S và số cào cào của Hưng
• Dòng thứ 2 là xâu \(S\) là xâu tạo được khi cào cào Hưng dính lại với nhau

Kết quả :

Ghi ra trên 1 dòng là số lần thực hiện phép thuật ít nhất

Ràng Buộc

\(N \leq 500\) , \(K \leq 500\);

Sample Input 1

Sample Input 2

Giải thích

• Test 1
• abc có thể biến thành aac abb acc đều chia được sao cho có 2 con cào cào của Hưng có tên là 1 xâu đối xứng
• Test 2
• không cần chia vì xâu ban đầu đã có thể chia thành 3 xâu đối xứng