// I AM A MUSLIM

#include "bits/stdc++.h"

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define fast_io std::ios::sync_with_stdio(0);std::cin.tie(0)
#define lli long long int
#define flush fflush(stdout)
#define new_line printf("\n")
#define yn(a, b) printf("%s\n", (a) >= (b) ? "Yes":"No")
#define amodm(a, M) (((a)%M+M)%M)
// #define int lli

using pii = std::pair<int,int>;

const int MOD = 1000000007;
const int mxN = 200100;

const int siz = 2001;
bool siv[siz];
std::vector<int> primes;
void sieve() {
    primes.push_back(2);
    siv[1] = 1;
    for (int i = 4; i < siz; i += 2) siv[i] = 1;
    for (int i = 3; i*i < siz; i += 2) {
        if (siv[i]==0) for (int j = i*i; j < siz; j += 2*i) siv[j] = 1;
    }
    for (int i = 3; i < siz; i += 2) {
        if (siv[i]==0) primes.push_back(i);
    }
}

signed main() {
    int testCases=1;
    scanf("%d",&testCases);
    
    sieve();
    
    for (int TC = 1; TC <= testCases; TC++) {
        int n;
        scanf("%d",&n);
        std::string s;
        std::cin >> s;
        int cnt[3]={0};
        for (auto &i : s) {
            cnt[i-'a']++;
        }
        std::vector<char> C = {'a', 'b', 'c'};
        
        int ans = 1e9;
        for (int i = 0; i < (int)primes.size()-2; i++) {
            for (int j = i+1; j < (int)primes.size()-1; j++) {
                if (primes[i]+primes[j] > n) continue;
                int a = primes[i];
                int b = primes[j];
                int c = n-a-b;
                if (siv[c] == 0) {
                    int at[] = {0, 1, 2};
                    do {
                        int local_ans = 0;
                        local_ans += std::max(0, cnt[C[at[0]]-'a'] - a);
                        local_ans += std::max(0, cnt[C[at[1]]-'a'] - b);
                        local_ans += std::max(0, cnt[C[at[2]]-'a'] - c);
                        ans = std::min(ans, local_ans);
                    } while (std::next_permutation(at, at+3));
                }
            }
        }
        
        auto calc = [&] (int i, int j, int k, int a, int b, int c) {
            return std::max(0, cnt[C[i]-'a'] - a) + std::max(0, cnt[C[j]-'a'] - b) + std::max(0, cnt[C[k]-'a'] - c);
        };
        
        for (int i = 0; i < (int)primes.size()-2; i++) {
            if (primes[i] > n) break;
            int a = primes[i];
            int b = n-a;
            if (siv[b] == 0) {
                // ab
                ans = std::min(ans, calc(0, 1, 2, a, b, 0));
                // ba
                ans = std::min(ans, calc(1, 0, 2, a, b, 0));
                // ac
                ans = std::min(ans, calc(0, 2, 1, a, b, 0));
                // ca
                ans = std::min(ans, calc(2, 0, 1, a, b, 0));
                // bc
                ans = std::min(ans, calc(1, 2, 0, a, b, 0));
                // cb
                ans = std::min(ans, calc(2, 1, 0, a, b, 0));
                // printf("%d %d : %d\n", a, b, ans);
            }
        }
        
        if (siv[n] == 0) {
            ans = std::min(ans, n-cnt[0]);
            ans = std::min(ans, n-cnt[1]);
            ans = std::min(ans, n-cnt[2]);
        }
        
        if (ans == 1e9) ans = -1;
        printf("%d\n", ans);
        
    }
    
    return 0;
}

/*

*/