#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
///Welcome to Nasif's Code
#define bug(var) cout<<#var<<" "<<var<<endl;
#define all(q) (q).begin(),(q).end()
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
int dx[]= {1,0,-1,0,1,-1,1,-1};
int dy[]= {0,1,0,-1,1,-1,-1,1};
bool isPrime[2001];
vector<vector<int> >primeRep[2001];
vector<int>primes;

void genPrimes()
{
    for(int i=0; i<=2000; i++)isPrime[i]=true;
    isPrime[1]=false;
    for(int i=2; i<=2000; i++)
    {
        if(!isPrime[i]) continue;
        for(int j=i+i; j<=2000; j+=i) isPrime[j]=false;
    }
    for(int i=1; i<=2000; i++)
    {
        if(isPrime[i])primes.push_back(i);
    }
}

void genPrimeRep()
{
    int sz = primes.size();

    for(int i=1; i<=2000; i++)
    {
        if(isPrime[i])
        {
            vector<int>v;
            v.push_back(0);
            v.push_back(0);
            v.push_back(i);

            primeRep[i].push_back(v);
        }
    }

    for(int i=0; i<sz; i++)
    {
        for(int j=i; j<sz; j++)
        {
            int x = primes[i]+primes[j];
            if(x<=2000)
            {
                vector<int>v;
                v.push_back(0);
                v.push_back(primes[i]);
                v.push_back(primes[j]);
                sort(all(v));
                primeRep[x].push_back(v);
            }
            for(int k=j; k<sz; k++)
            {
                int x = primes[i]+primes[j]+primes[k];
                if(x<=2000)
                {
                    vector<int>v;
                    v.push_back(primes[i]);
                    v.push_back(primes[j]);
                    v.push_back(primes[k]);
                    sort(all(v));
                    primeRep[x].push_back(v);
                }

            }
        }
    }
}
void ignite()
{
    int n;
    cin>>n;
    string s;
    cin>>s;

    int mp[3]= {0};

    for(auto it:s)
    {
        mp[it-'a']++;
    }

    vector<int>v;

    for(int i=0; i<3; i++)
        if(mp[i])
            v.push_back(mp[i]);
    while(v.size()<3)v.push_back(0);
    sort(all(v));
    if(primeRep[n].size()==0) cout<<"-1"<<endl;
    else
    {
        int ans=1e9;
        for(auto it:primeRep[n])
        {
            int dif=0;
            for(int i=0; i<3; i++)
            {
                dif+=abs(v[i]-it[i]);
            }
            dif/=2;
            ans=min(ans,dif);
        }
        cout<<ans<<endl;
    }


}
int main()
{
    FastRead
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    genPrimes();
    genPrimeRep();
    int tc=1;
    cin>>tc;
    while(tc--)
        ignite();


    return 0;
}