단백질

마그누스는 생물학자다. 하루 종일 단백질을 다루면서 이 분자가 어떻게 생겼는지 보고 싶어 한다. 황 원자가 많이 들어 있는 단백질은 X선 결정학으로 이미지를 얻을 수 있다는 이야기를 들었다. 자기 단백질에는 황이 부족하다고 생각하지만, 이미지를 얻기 위해서라면 단백질을 바꿀 생각이 있다. 단백질은 마그누스가 키우는 박테리아가 만들어 주고 있고, 그는 이 박테리아에 돌연변이를 일으켜 단백질을 바꾸려고 한다.

마그누스는 단백질을 만드는 DNA 문자열과 그 DNA가 아미노산 서열로 번역되는 방식을 알고 있다. 코드의 처음 세 글자가 첫 번째 아미노산을 정하고, 그다음 세 글자가 두 번째 아미노산을 정하며, 이런 식으로 이어진다. 그 세 글자가 순서대로 ATG이면 아미노산 메티오닌이 단백질에 들어간다. 메티오닌에는 황 원자가 있으므로 마그누스는 단백질에 메티오닌이 많이 들어가기를 원한다.

마그누스가 DNA 코드에 가할 수 있는 변화는 글자를 삽입하는 것뿐이다. 삽입하는 글자는 A, T, G, C 중 하나이고 문자열의 어느 위치에나 넣을 수 있다. 글자 하나를 넣는 데 시간이 아주 오래 걸리므로 삽입은 최대한 적게 하고 싶다. 코드가 메티오닌을 $n$개 이상 만들도록 하려면 글자를 최소 몇 개 삽입해야 하는지 구하라.

완성된 문자열은 앞에서부터 세 글자씩 끊어 읽는다. 세 글자로 이루어진 각 묶음을 블록이라고 하자. 맨 뒤에 세 글자를 채우지 못하고 남은 글자는 블록을 이루지 않는다. ATG와 같은 블록은 메티오닌을 하나 만든다.

예를 들어 TGATGC는 메티오닌을 하나도 만들지 않지만, 맨 앞에 A를 삽입해 ATGATGC로 만들면 앞의 두 블록이 모두 ATG가 되어 메티오닌을 두 개 만든다.

첫째 줄에 단백질이 담아야 하는 메티오닌의 개수 $n$이 주어진다. ($1 \le n \le 10^6$)

둘째 줄에 DNA 문자열이 주어진다. 길이는 1 이상 1000 이하이고, 각 글자는 A, T, G, C 중 하나다.

DNA 문자열의 세 글자 블록 중 적어도 $n$개가 ATG가 되도록 만들 때 삽입해야 하는 글자의 최소 개수를 한 줄에 출력한다.