유전자 주기 분석

A, C, G, T로 이루어진 길이 N의 유전자 문자열이 있다. 이 문자열을 최대 주기 M을 갖는 주기문으로 바꾸려 한다. 주기 P란 문자열의 i번째 문자가 (i mod P)번째 문자와 같음을 의미한다(0-indexed).

문자열에서 최소 몇 글자를 바꿔야 주기 P (1 <= P <= M)를 갖는 주기문이 되는지 구하시오.

입력

첫째 줄에 최대 주기 M이 주어진다. (1 <= M <= 3000)
둘째 줄에 길이 N의 유전자 문자열이 주어진다. (1 <= N <= 3000, 문자열은 A, C, G, T로만 구성됨)

출력

주기문으로 바꾸기 위해 변경해야 하는 최소 글자 수를 출력한다.

입출력 예시

입력 1

4
ACGTACGT

출력 1

0

입력 2

3
ACACGCAC

출력 2

1