#include <bits/stdc++.h>
using namespace std;
int k,ans=1,len;
string s;
bool check(){
	int cnt = 0;
	for(int i = 0;i < ans;i++){
		int j = i;
		while(j + ans < len){
			j += ans;
			if(s[j] != s[i]) cnt++;
		}
		if(cnt > k) return 0;
	}
	if(cnt <= k) return 1;
	else return 0;
}
int main(){
	cin>>k;
	cin>>s;
	len = s.length();
	for(ans=1;ans<=len;ans++) if(len % ans == 0 && check()) break;
	if(ans > len) ans = len;
	cout<<ans;
	return 0;
}

https://www.luogu.com.cn/record/169037636