Cho xâu \(S\) có độ dài \(n\) và một số nguyên \(k(1\le k\le n)\). Xâu \(S\) có "độ đẹp" là \(x\), nếu \(x\) là số nguyên không âm lớn nhất thỏa mãn:

• Trong \(S\) tồn tại \(x\) xâu con (gồm những phần tử liên tiếp) có độ dài là \(k\) và chúng không được chồng lên nhau

• Tất cả các phần tử của \(x\) xâu con này phải giống nhau.

Yêu cầu: Cho số nguyên \(k\) và xâu \(S\) có độ dài là \(n\). Tìm "độ đẹp" của \(S\)

Input

• Dòng thứ nhất chứa hai số nguyên \(n\) và \(k(1\le k\le n\le 2.10^5)\)

• Dòng thứ hai chứa xâu \(S\) có độ dài là \(n\)

Output

• In ra đáp án cần tìm

Example

4 2
aabb

1

7 2
aabbbaa

2