Since the constraint of N is <= 2000, We precompute all the primes upto N and store them in an array using Sieve. Then we run a 3 nested loop brute force to check all the possible prime combinations that satisfies p1 + p2 + p3 == n. and greedily try to match the frequency of each character. Our answer will be the minimum cost out of all of them. And do not forget to insert 0 in the prime array. Since we can completely remove a character

#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
// #include "template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

#define F first
#define S second
// #define int long long
#define double long double
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define mp(x, y) make_pair(x, y)
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define INF (int)1e8
using namespace std;

using pii = pair<int, int>;
using pdd = pair<double, double>;
using pbb = pair<bool, bool>;
using pcc = pair<char, char>;
using pss = pair<string, string>;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vpii = vector<pair<int, int>>;
using vpdd = vector<pair<double, double>>;
using vpbb = vector<pair<bool, bool>>;
using vpcc = vector<pair<char, char>>;
using vpss = vector<pair<string, string>>;
using vvi = vector<vector<int>>;
using vvd = vector<vector<double>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using vvpii = vector<vector<pair<int, int>>>;
using vvpdd = vector<vector<pair<double, double>>>;
using vvpbb = vector<vector<pair<bool, bool>>>;
using vvpcc = vector<vector<pair<char, char>>>;
using vvpss = vector<vector<pair<string, string>>>;

// clang-format off
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T> T sqrt_(T elem) {int l=1,r=elem;while(l<=r){int mid=l+(r-l)/2LL;if(mid>elem/mid){r=mid-1;}else{int val=mid*mid;if(val<=elem){l=mid+1;}else{r=mid-1;}}}return r;}
template <class T> T ceil_(T a,T b) {return(a+b-1)/b;};
template <class T> T mod_add(T a,T b,T mod){return((a%mod)+(b%mod))% mod;}
template <class T> T mod_sub(T a,T b,T mod){return((a%mod)-(b%mod)+mod)%mod;}
template <class T> T mod_mul(T a,T b,T mod){return((a%mod)*(b%mod))%mod;}
template <class T> T mod_inv(T a,T mod){T m0=mod,y=0,x=1;if(mod==1)return 0;while(a>1){T q=a/mod;T t=mod;mod=a%mod,a=t;t=y;y=x-q*y;x=t;}if(x<0)x+=m0;return x;}
template <class T> T mod_div(T a,T b,T mod){return mod_mul(a,mod_inv(b,mod),mod);}
// clang-format on
const int N = 2000;
vb isPrime(N + 1, true);
vi res;

void preCompute() {
  isPrime[0] = isPrime[1] = false;
  for (int i = 2; i * i <= N; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j <= N; j += i) {
        isPrime[j] = false;
      }
    }
  }

  res.eb(0);

  for (int i = 2; i <= N; ++i) {
    if (isPrime[i]) {
      res.eb(i);
    }
  }
}
void solve() {
  int n;
  string s;
  cin >> n >> s;

  int a = 0, b = 0, c = 0;

  for (int i = 0; i < n; ++i) {
    if (s[i] == 'a') {
      ++a;
    } else if (s[i] == 'b') {
      ++b;
    } else {
      ++c;
    }
  }

  int ans = INF;

  for (int i = 0; i < sz(res); ++i) {
    int v1 = res[i];
    if (v1 > n) {
      break;
    }
    for (int j = 0; j < sz(res); ++j) {
      int v2 = res[j];
      if (v1 + v2 > n) {
        break;
      }
      for (int k = 0; k < sz(res); ++k) {
        int v3 = res[k];
        int total = v1 + v2 + v3;
        if (total > n) {
          break;
        }

        if (total == n) {
          int val = 0, curr = 0;

          if (a <= v1) {
            curr += v1 - a;
            val += v1 - a;
          } else {
            curr += a - v1;
            val += -(a - v1);
          }

          // if (v1 == 0 && v2 == 0 && v3 == 5) {
          //   debug(curr, val);
          // }

          if (b <= v2) {
            if (val < 0) {
              val += v2 - b;
              if (val > 0) {
                curr += val;
              }
            } else {
              val += v2 - b;
              curr += v2 - b;
            }
          } else {
            if (val > 0) {
              val += -(b - v2);
              if (val < 0) {
                curr += abs(val);
              }
            } else {
              val += -(b - v2);
              curr += abs(b - v2);
            }
          }

          // if (v1 == 0 && v2 == 0 && v3 == 5) {
          //   debug(curr, val);
          // }

          if (c <= v3) {
            if (val < 0) {
              val += v3 - c;
              if (val > 0) {
                curr += val;
              }
            } else {
              val += v3 - c;
              curr += v3 - c;
            }
          } else {
            if (val > 0) {
              val += -(c - v3);
              if (val < 0) {
                curr += abs(val);
              }
            } else {
              val += -(c - v3);
              curr += abs(c - v3);
            }
          }

          // if (v1 == 0 && v2 == 0 && v3 == 5) {
          //   debug(curr, val);
          // }
          // debug(v1, v2, v3, curr);
          ans = min(ans, curr);
        }
      }
    }
  }

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

signed main() {

  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  int tt = 1, count = 1;
  preCompute();
  cin >> tt;
  while (tt--) {
    // cout << "Case #" << count << ": ";
    solve();
    ++count;
  }
  return 0;
}