#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

int minOperationsToBeautiful(int N, string &S) {
    vector<int> freq(3, 0); // freq[0]: 'a'; freq[1]: 'b'; freq[2]: 'c'
    for (char ch : S) {
        if (ch == 'a') ++freq[0];
        else if (ch == 'b') ++freq[1];
        else if (ch == 'c') ++freq[2];
    }

    int total_changes = 0;

    // Decompose to individual operations for clarity and speed
    for (int i = 0; i < 3; ++i) {
        if (!isPrime(freq[i])) {
            int left_freq = freq[i], right_freq = freq[i];
            int left_changes = 0, right_changes = 0;

            // Lower side nearest prime
            while (!isPrime(left_freq) && left_freq > 0) {
                --left_freq;
                ++left_changes;
            }

            // Higher side nearest prime
            while (!isPrime(right_freq)) {
                ++right_freq;
                ++right_changes;
            }

            total_changes += min(left_changes, right_changes);
        }
    }

    return total_changes > N ? -1 : total_changes;
}

int main() {
    int T;
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;

    while (T--) {
        int N;
        string S;
        cin >> N >> S;

        cout << minOperationsToBeautiful(N, S) << '\n';
    }

    return 0;
}