A. Выпьем?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Всем известно, что жители Берляндии ведут здоровый образ жизни. Особенно студенты. Берляндские студенты настолько суровы, что пьют исключительно апельсиновый сок!

Вот и вчера на шашлыках студент Вася и его одногруппники употребляли лишь этот полезный напиток. После того как закончился первый ящик сока, они решили сыграть в одну простую игру. Все n человек, присутствовавшие на шашлыках, сели в круг (каждый получил, таким образом, уникальный номер bi от 0 до n - 1). Начинал игру человек под номером 0 (в этот раз это был Вася). Все ходы в игре нумеровались целыми числами, начиная с 1. Если j-ый ход доставался человеку с номером bi, то этот человек действовал следующим образом:

  1. он показывал на человека с номером (bi + 1) mod n либо локтем, либо кивком головы (x mod y — остаток от деления x на y);
  2. если j ≥ 4 и игроки, совершавшие ходы под номерами j - 1, j - 2, j - 3, во время этих ходов сделали то же движение, что и игрок bi на текущем ходу, то он выпивал стакан сока;
  3. ход передавался человеку с номером (bi + 1) mod n.

Человек, на которого показал игрок, ходивший последним, уже не совершал никаких действий.

К сожалению, Вася выпил слишком много сока и уже не помнит, в чем заключалась цель игры. Однако у Васи осталась записанная последовательность действий всех участников (включая его самого). Теперь Вася хочет выяснить, какое наибольшее количество сока он мог бы выпить, если бы действовал оптимально (при неизменных действиях других игроков). Помогите ему.

Можно считать, что при любом варианте развития событий сока хватило бы на всех.

Входные данные

В первой строке записано единственное целое число n (4 ≤ n ≤ 2000) — количество участников игры. Вторая строка описывает саму игру: i-ый символ этой строки равен 'a', если участник, ходивший i-ым, показал на следующего человека локтем, и 'b' — если кивком головы. Игра продолжалась не менее 1 и не более 2000 ходов.

Выходные данные

Выведите единственное целое число — количество стаканов сока, которое выпил бы Вася, если бы действовал оптимально.

Примеры
Входные данные
4
abbba
Выходные данные
1
Входные данные
4
abbab
Выходные данные
0
Примечание

В обоих примерах Васе доставались два хода — 1 и 5. В первом примере Вася мог выпить стакан сока во время пятого хода, если бы показал на следующего человека кивком головы. В этом случае последовательность ходов имела бы вид «abbbb». Во втором примере Вася в любом случае не выпил бы ни одного стакана сока, поскольку движения, сделанные во время 3 и 4 ходов, отличаются.