/*
 *   Copyright (c) 2025 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
bool iscomp[20000];
vector<int> primes;
void seive()
{
    iscomp[1] = true;
    for(int i=2;i<20000;i++)
    {
        if(iscomp[i]) continue;
        for(int j=i+i;j<20000;j+=i) iscomp[j]=true;
    }
    primes.push_back(0);
    for(int i=2;i<3000;i++)
    {
        if(!iscomp[i]) primes.push_back(i);
    }
}

void solve()
{
    int n; cin >> n;
    string s; cin >> s;
    int a=0,b=0,c=0;
    for(auto e:s)
    {
        a += (e=='a');
        b += (e=='b');
        c += (e=='c');
    }
    vector<vector<int>> v;
    int m = primes.size();
    for(int i=0;i<m;i++)
    {
        for(int j=i;j<m;j++)
        {
            int need = n-primes[i]-primes[j];
            if(need < primes[j]) break;
            if(!iscomp[need]) v.push_back({primes[i],primes[j],need});
        }
    }
    if(v.empty()) {cout<<-1<<endl; return;}
    vector<int> abc;
    abc.push_back(a);
    abc.push_back(b);
    abc.push_back(c);
    sort(abc.begin(),abc.end());
    int ans = 1e9;
    for(auto e:v)
    {
        ans = min(ans , (abs(abc[0]-e[0])+abs(abc[1]-e[1])+abs(abc[2]-e[2])) /2 );
    }
    cout<<ans<<endl;
}

int main()
{
    seive();
    int t; cin >> t; while(t--) solve();
}