Magnus 是一位生物学家。他整天都在研究蛋白质，现在他想知道这些分子长什么样。他听说 X 射线晶体学可以用来获取含有大量硫原子的蛋白质图像。Magnus 认为他的蛋白质含硫量不足，但他愿意为了让实验成功而对其进行改造。Magnus 有培养这些蛋白质的细菌，他计划通过诱变这些细菌来改变蛋白质。

Magnus 了解编码其蛋白质的 DNA 序列，以及 DNA 如何翻译成构成蛋白质的氨基酸序列。代码中的前三个字母决定第一个氨基酸，接下来的三个字母决定第二个，依此类推。每当这三个字母为 ATG（按此顺序）时，氨基酸甲硫氨酸（methionine）就会被整合到蛋白质中。甲硫氨酸含有一个硫原子，因此 Magnus 希望他的蛋白质中含有尽可能多的甲硫氨酸。Magnus 只能通过插入字母来改变 DNA 代码。然而，每插入一个字母都需要花费大量时间。既然你擅长计算机技术，他请求你的帮助。你能算出为了使 DNA 代码编码出 $n$ 个甲硫氨酸，最少需要插入多少个字母吗？

例如，DNA 字符串 TGATGC 编码不出任何甲硫氨酸，但在开头添加一个 A 后，它变成了 ATGATGC，其中包含两个 ATG 块，因此编码出两个甲硫氨酸。这是第一个样例输入，第二个样例输入的解决方案如下图所示。

输入格式

第一行包含一个正整数 $n \le 10^6$，表示蛋白质中需要包含的甲硫氨酸数量。第二行包含一个非空的 DNA 字符串，长度最多为 1000 个字母，每个字母均为 A、T、G 或 C 中的一个。

输出格式

输出一个整数，表示为了使 DNA 字符串中至少有 $n$ 个三字母块为 ATG，最少需要插入的字母数量。

样例

输入格式 1

2
TGATGC

输出格式 1

1

输入格式 2

4
ATCATGCATGATGTG

输出格式 2

3