from itertools import permutations
import math

MOD = 998244353
M = 2e5 + 10
MAX_N = 2000

# List of all permutations of 'abc'
all_permutations = []

# Prime numbers up to 2000
primes = []
# Prime presence for numbers up to 2000
is_prime = [0] * (MAX_N + 1)

def precal():
    # Generate all permutations of "abc"
    s = "abc"
    all_permutations.append(s)
    for perm in permutations(s):
        all_permutations.append(''.join(perm))
    
    # Sieve of Eratosthenes to find primes up to MAX_N
    is_prime[0] = 0
    is_prime[1] = 1
    primes.append(0);
    for i in range(2, MAX_N + 1):
        if is_prime[i] == 0:
            primes.append(i)
            for j in range(i * 2, MAX_N + 1, i):
                is_prime[j] = 1

def main():
    # Read number of test cases
    t = int(input())
    
    # Precompute necessary data
    precal()

    # Process each test case
    for _ in range(t):
        # Read n and the string s
        n = int(input())
        s = input().strip()

        # Frequency count of 'a', 'b', 'c' in the string
        fre = [0] * 3
        for char in s:
            fre[ord(char) - ord('a')] += 1

        # Initialize the result with a large value
        mx = M

        # Iterate over all permutations of "abc"
        for perm in all_permutations:
            # For each prime pair (start, end) where start + end <= n
            for start in primes:
                if start > n:
                    break
                for end in primes:
                    if start + end > n:
                        break
                    baki = n - (start + end)
                    if  is_prime[baki]==1:
                        continue
                    
                    # Frequencies of characters in the current permutation
                    a = fre[ord(perm[0]) - ord('a')]
                    b = fre[ord(perm[1]) - ord('a')]
                    c = fre[ord(perm[2]) - ord('a')]

                    pos = 0
                    neg = 0

                    # Calculate how much we need to add or remove to match the prime requirements
                    if a > start:
                        pos += a - start
                    if a < start:
                        neg += start - a
                    if b > end:
                        pos += b - end
                    if b < end:
                        neg += end - b
                    if c > baki:
                        pos += c - baki
                    if c < baki:
                        neg += baki - c
                    
                    # Minimize the result
                    mx = min(mx, min(pos, neg))

        # If no valid answer found, return -1
        if mx == M:
            mx = -1
        
        # Output the result for the current test case
        print(mx)

# Execute the main function
if __name__ == "__main__":
    main()