众所周知,柏林公民热衷于健康,尤其是学生。伯兰的学生太厉害了,他们只喝橙汁!
昨天,一位学生Vasya和他的伙伴们做了一些烧烤,他们只喝了这种健康饮料。当他们用完第一桶果汁后,他们决定玩一个简单的游戏。所有来烧烤的n个人围成一圈(这样每个人都会收到一个从0到n-1的唯一索引bi)。 0号人开始了游戏(这次是Vasya)。游戏中的所有回合均以从 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。
最后一个回合被指的人没有做出任何动作。
问题是,瓦夏喝了太多果汁,记不起比赛的目标了。然而,瓦夏得到了所有参与者(包括他自己)的行动顺序记录。现在 Vasya 想要找出如果他表现最佳(其他玩家的行为不变),他可以喝的最大果汁量。帮助他。
您可以假设在任何情况下,每个人都有足够的果汁。
输入
第一行包含一个整数 n (4 ≤ n ≤ 2000) — 游戏参与者的数量。第二行描述了实际的游戏:如果第 i 个移动的参与者用肘部指向下一个人,则该行的第 i 个字符等于“a”;如果参与者点头指向下一个人,则该行的第 i 个字符等于“b”。游戏持续至少1轮,最多2000轮。
输出
打印一个整数——如果 Vasya 表现最佳,他可以喝下的果汁杯数。
示例
输入 #1
4 abbba
输出 #1
1
输入 #2
4 abbab
输出 #2
0
注意
在两个样本中,Vasya 都有两个回合 - 1 和 5。在第一个样本中,如果 Vasya 指向下一个人点头,他可能会在第五回合喝下一杯果汁。在这种情况下,移动顺序将类似于“abbbb”。在第二个样本中,Vasya 不会喝一杯果汁,因为第 3 回合和第 4 回合执行的动作不同。