Cạn ly nào!

Có $n$ người ngồi thành một vòng tròn, đánh số từ $0$ đến $n-1$. Người số $0$ thực hiện lượt đầu tiên. Các lượt chơi được đánh số bắt đầu từ $1$.

Ở lượt thứ $j$, gọi $b$ là chỉ số của người đang chơi. Người này:

1. chỉ vào người có chỉ số $(b+1)modn$ bằng một trong hai cử chỉ: khuỷu tay (ký hiệu a) hoặc cái gật đầu (ký hiệu b);
2. nếu $j\ge 4$ và ba lượt trước đó (lượt $j-1$, $j-2$, $j-3$) đều sử dụng đúng cùng cử chỉ mà người này vừa sử dụng ở lượt $j$, thì người này được uống một ly nước cam;
3. lượt chơi được chuyển sang người có chỉ số $(b+1)modn$.

Người được chỉ vào ở lượt cuối cùng không thực hiện hành động nào.

Vasya là người số $0$. Cho trước chuỗi cử chỉ thực tế đã diễn ra trong toàn bộ trò chơi. Vasya muốn biết: nếu được chơi lại một cách tối ưu (chỉ thay đổi cử chỉ của chính Vasya ở các lượt của mình, các cử chỉ của những người khác giữ nguyên), thì Vasya có thể uống được tối đa bao nhiêu ly nước cam?

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên $n$ — số người chơi.
• Dòng thứ hai chứa một chuỗi mô tả các cử chỉ đã diễn ra: ký tự thứ $i$ là a nếu người chơi ở lượt $i$ chỉ bằng khuỷu tay, là b nếu chỉ bằng cái gật đầu.

Dữ liệu ra

In ra một số nguyên duy nhất — số ly nước cam tối đa Vasya có thể uống được.

Ràng buộc

• $4\le n\le 2000$.
• Chuỗi cử chỉ có độ dài từ $1$ đến $2000$.

Ví dụ