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

pair<vector<bool>, vector<int>> sieve(int max_limit)
{
    vector<bool> is_prime(max_limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= sqrt(max_limit); ++i)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= max_limit; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
    vector<int> primes;
    for (int i = 2; i <= max_limit; ++i)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
        }
    }
    return {is_prime, primes};
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    pair<vector<bool>, vector<int>> see = sieve(2000);
    vector<bool> is_prime = see.first;
    vector<int> primes = see.second;

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        int count_a = 0, count_b = 0, count_c = 0;
        for (char ch : s)
        {
            if (ch == 'a')
                count_a++;
            else if (ch == 'b')
                count_b++;
            else if (ch == 'c')
                count_c++;
        }
        int mn = INT32_MAX;
        for (int mask = 1; mask < (1 << 3); mask++)
        {
            vector<char> vis;
            if (mask & 1)
                vis.push_back('a');
            if (mask & 2)
                vis.push_back('b');
            if (mask & 4)
                vis.push_back('c');
            int k = vis.size();
            if (k == 1)
            {
                char x = vis[0];
                if (is_prime[n])
                {
                    int sum_overlap = 0;
                    if (x == 'a')
                        sum_overlap = min(count_a, n);
                    else if (x == 'b')
                        sum_overlap = min(count_b, n);
                    else if (x == 'c')
                        sum_overlap = min(count_c, n);
                    int changes = n - sum_overlap;
                    mn = min(mn, changes);
                }
            }
            else if (k == 2)
            {
                char x = vis[0];
                char y = vis[1];
                for (auto p_x : primes)
                {
                    if (p_x > n - 2)
                        break;
                    int p_y = n - p_x;
                    if (p_y < 2)
                        continue;
                    if (is_prime[p_y])
                    {
                        int sum_overlap = 0;
                        if (x == 'a')
                            sum_overlap += min(count_a, p_x);
                        else if (x == 'b')
                            sum_overlap += min(count_b, p_x);
                        else if (x == 'c')
                            sum_overlap += min(count_c, p_x);

                        if (y == 'a')
                            sum_overlap += min(count_a, p_y);
                        else if (y == 'b')
                            sum_overlap += min(count_b, p_y);
                        else if (y == 'c')
                            sum_overlap += min(count_c, p_y);

                        int changes = n - sum_overlap;
                        mn = min(mn, changes);
                    }
                }
            }
            else if (k == 3)
            {
                char x = vis[0];
                char y = vis[1];
                char z = vis[2];
                for (auto p_x : primes)
                {
                    if (p_x > n - 4)
                        break;
                    for (auto p_y : primes)
                    {
                        if (p_x + p_y > n - 2)
                            break;
                        int p_z = n - p_x - p_y;
                        if (p_z < 2)
                            continue;
                        if (is_prime[p_z])
                        {
                            int sum_overlap = 0;
                            if (x == 'a')
                                sum_overlap += min(count_a, p_x);
                            else if (x == 'b')
                                sum_overlap += min(count_b, p_x);
                            else if (x == 'c')
                                sum_overlap += min(count_c, p_x);

                            if (y == 'a')
                                sum_overlap += min(count_a, p_y);
                            else if (y == 'b')
                                sum_overlap += min(count_b, p_y);
                            else if (y == 'c')
                                sum_overlap += min(count_c, p_y);

                            if (z == 'a')
                                sum_overlap += min(count_a, p_z);
                            else if (z == 'b')
                                sum_overlap += min(count_b, p_z);
                            else if (z == 'c')
                                sum_overlap += min(count_c, p_z);

                            int changes = n - sum_overlap;
                            mn = min(mn, changes);
                        }
                    }
                }
            }
        }
        if (mn != INT32_MAX)
        {
            cout << mn << "\n";
        }
        else
        {
            cout << "-1\n";
        }
    }
}