// Animesh Fatehpuria

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

const int N = 1000000 + 50;

int a[N], spf[N];
map < int, vector < int > > indices;

inline int pulverize(int x, int prime, int isOdd) {
    int ans = 0;
    while (x % prime == 0) {
        ans += 1;
        x /= prime;
    }
    if (ans % 2 == isOdd) {
        return 0;
    } else {
        return 1;
    }
}

int main() {
    for (int i = 2; i < N; i++) {
        if (!spf[i]) {
            for (int j = i + i; j < N; j += i) {
                if (!spf[j]) {
                    spf[j] = i;
                }
            }
            spf[i] = i;
        }
    }
    int t; scanf("%d", &t);
    while (t--) {
        indices.clear();
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        vector < int > primes;
        for (int i = 1; i <= n; i++) {
            int x = a[i];
            while (x != 1) {
                primes.push_back(spf[x]);
                indices[spf[x]].push_back(i);
                x /= spf[x];
            }
        }
        sort(primes.begin(), primes.end());
        primes.resize(unique(primes.begin(), primes.end()) - primes.begin());
        int ans = 0;
        for (int prime : primes) {
            indices[prime].resize(unique(indices[prime].begin(), indices[prime].end()) - indices[prime].begin());
            int oddCost = 0, evenCost = 0;
            for (int i : indices[prime]) {
                oddCost += pulverize(a[i], prime, 1);
                evenCost += pulverize(a[i], prime, 0);
            }
            oddCost += (n - (int) indices[prime].size());
            ans += min(oddCost, evenCost);
        }
        cout << ans << '\n';
    }
}