#include <bits/stdc++.h>

using namespace std;

long long ans = LLONG_MAX, k, l, cnt, prim[10000001];
char s[10000001];

int main() {
    scanf("%lld%s", &k, s + 1);
    l = strlen(s + 1);
    prim[++cnt] = 1;
    for (long long i = 2; i * i <= l; i++)
        if (!(l % i)) {
            if (i * i == l)
                prim[++cnt] = i;
            else {
                prim[++cnt] = i;
                prim[++cnt] = l / i;
            }
        }
    prim[++cnt] = l;
    sort(prim + 1, prim + cnt + 1);
    for (long long i = 1; i <= cnt; i++) {
        if (prim[i] >= ans)
            continue;
        long long sum = 0;
        for (long long j = 1; j <= prim[i]; j++)
            for (long long k = j + prim[i]; k <= l; k += prim[i])
                if (s[k] != s[j])
                    ++sum;
        if (sum <= k) {
            printf("%lld\n", prim[i]);
            return 0;
        }
    }
    return 0;
}
//3 apollo