TREE

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

const int inf = 1e9 + 7;
int t, n;
long long a[10], npd[10], dp[10][1<<10];

void megumi() {
    scanf("%d", &n); long long ans = inf;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < (1<<n); j++) dp[i][j] = inf;
    }
    for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
    sort(a, a + n);
    for(int i = 0; i < n; i++) {
        long long k = a[i], p = sqrt(k); bool isPrime = true; npd[i] = 0;
        for(int j = 2; j <= p; j++) {
            if(k % j == 0) {
                isPrime = false;
                while(k % j == 0) k /= j, npd[i]++;
            }
        }
        if(k > 1) npd[i]++;
        if(not isPrime) npd[i]++;
        //cout << i << " " << npd[i] << "\n";
    }
    dp[0][1<<(n-1)] = npd[0];
    for(int i = 1; i < n; i++) {
        for(int prev = 1; prev < (1<<(i+1)); prev++) {
            for(int cur = 1; cur < (1<<(i+1)); cur++) {
                int m1 = (prev<<(n-i-1)), m2 = (cur<<(n-i-1)), tot = npd[i];
                //cout << "mask " << m1 << " " << m2 << "\n";
                long long res = a[i]; bool pos = true, numofSubtree = false;
                if(not (cur&1)) continue;
                for(int l = i; l > 0; l--) {
                    //cout << l << " " << ((prev>>l)&1) << " " << ((cur>>l)&1) << "\n";
                    if((not ((prev>>l)&1)) && ((cur>>l)&1)) {
                        pos = false;
                        break;
                    }
                    else if(((prev>>l)&1) && not ((cur>>l)&1)) {
                        //cout << a[i-l] << " has been multiplied to the root\n";
                        if(res % a[i-l] != 0) {
                            pos = false;
                            break;
                        }
                        else res /= a[i-l], tot -= npd[i-l] - (npd[i-l] > 1);
                    }
                    else if(((prev>>l)&1) && ((cur>>l)&1)) numofSubtree = 1;
                }
                if(not pos) continue;
                long long current_res = dp[i-1][m1] + tot, initnumofSubtree = __builtin_popcount(prev);
                if(initnumofSubtree > 1 && not numofSubtree) current_res--;
                else if(initnumofSubtree == 1 && numofSubtree) current_res++;
                dp[i][m2] = min(dp[i][m2], current_res);
            }
        }
        //cout << "consider to " << i << "th number\n";
        //for(int j = 1; j < (1<<(i+1)); j++) cout << (j<<(n-i-1)) << " " << dp[i][(j<<(n-i-1))] << "\n";
    }
    for(int j = 1; j < (1<<n); j++) ans = min(ans, dp[n-1][j]);
    printf("%lld\n", ans);
}

int main() {
    freopen("test.txt", "r", stdin);
    scanf("%d", &t);
    while(t--) megumi();
}