1512번 - 주기문으로 바꾸기

문제

세준이는 생물학자이다. 따라서 DNA를 가지고 연구하는 일이 많다. 어느 날 세준이는 이렇게 긴 문자열을 보는 것이 너무 지겨워서 간단하게 나타내고 싶었다.

주어진 DNA가 길이 $L$일 때, 주기의 길이가 $P$라면, 0ドル ≤ i ≤ L-P-1$ 인 모든 $i$에 대해서 $i+p$에 위치에 있는 문자와 같을 때를 말한다. 예를 들어, "CATCATC", "CATCAT", "ACTAC", "ACT"는 모두 길이가 3ドル$인 주기문이다.

DNA 문자열이 주어졌을 때, 이걸 길이 $M$보다 작거나 같은 주기문으로 바꿀 때, 바꾸는 문자열의 개수를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 $M$이 주어진다. $M$은 문자열의 길이보다 작거나 같다. 둘째 줄에 문자열이 주어진다. 문자열은 A, C, G, T로만 이루어져 있다. 문자열의 길이는 3000ドル$보다 작거나 같다.

출력

첫째 줄에 바꾸는 문자의 개수를 출력한다.

제한

힌트