#include <bits/stdc++.h>
using namespace std;

//template
#pragma region 
const int MOD = 1e9 + 7;

#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;

template<class T> using ordset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;


struct mi {
    int v;
    explicit operator int() const { return v; }
    mi() { v = 0; }
    mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi &operator+=(mi &a, mi b) {
    if ((a.v += b.v) >= MOD) a.v -= MOD;
    return a;
}
mi &operator-=(mi &a, mi b) {
    if ((a.v -= b.v) < 0) a.v += MOD;
    return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi &operator*=(mi &a, mi b) { return a = a * b; }
mi mypow(mi a, long long p) {
    assert(p >= 0);
    return p == 0 ? 1 : mypow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
    assert(a.v != 0);
    return mypow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }

#define all(x) x.begin(), x.end()
#define lef(x) (x << 1)
#define rig(x) (lef(x) | 1)
#define ft first
#define sd second
#define mt make_tuple
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define dbg(x) cout << #x << " = " << x << '\n';
#define rep(i, begin, end) for (__typeof(begin) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdb;
// typedef __int128_t lll;

template<typename T, typename T1>
ostream & operator<<(ostream &os, pair<T, T1> p){
    os << "(" << p.ft << "," << p.sd << ")";
    return os;
}

template<typename T, typename T1>
istream & operator>>(istream &is, pair<T, T1>& p){
    is >> p.ft >> p.sd;
    return is;
}

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#pragma endregion

const int N = 1e5 + 30;
ll n, m, k;
ll x[N];
string s;
char vis[2020];
set<int> pl;


void sieve(){
    for(int i = 2; i * i < 2010; i++){
        if(!vis[i]){
            for(int j = i + i; j < 2010; j += i) vis[j] = 1;
        }
    }

    rep(i,2,2010){
        if(!vis[i]) pl.insert(i);
    }

}



void test() {
    cin >> n >> s;
    ll a, b, c;
    a  = b = c = 0;
    rep(i,0,n){
        if(s[i] == 'a') a++;
        else if(s[i] == 'b') b++;
        else c++;
    }

    if(n == 1){
        cout << -1 << '\n';
        return;
    }

    ll cust = 1e9;
    for(auto i: pl){
        if(i > n) break;
        for(auto j: pl){
            if(pl.find(n - i - j) != pl.end()){
                cust = min(cust, (abs(a - i) + abs(b - j) + abs((n - i - j) - c))/2);
                cust = min(cust, (abs(a - i) + abs(c - j) + abs((n - i - j) - b))/2);
                cust = min(cust, (abs(b - i) + abs(a - j) + abs((n - i - j) - c))/2);
                cust = min(cust, (abs(b - i) + abs(c - j) + abs((n - i - j) - a))/2);
                cust = min(cust, (abs(c - i) + abs(a - j) + abs((n - i - j) - b))/2);
                cust = min(cust, (abs(c - i) + abs(b - j) + abs((n - i - j) - a))/2);
            }
        }
        if(pl.find(n - i) != pl.end()){
            cust = min(cust, (abs(a - i) + (n - i) + 1)/2);
            cust = min(cust, (abs(b - i) + (n - i) + 1)/2);
            cust = min(cust, (abs(c - i) + (n - i) + 1)/2);
        }

    }
    cout << cust << '\n';

}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    sieve();
    pl.insert(0);

    int te = 1;
    cin >> te;
    while(te--) test();
    
    return 0;
}