Untitled

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define AboTaha_on_da_code ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define X first
#define Y second

const int dx[8]={0, 0, 1, -1, 1, -1, -1, 1};
const int dy[8]={1, -1, 0, 0, 1, -1, 1, -1};
const double EPS = 1e-8;
const int mod = 1e9+7; // 1e9+7, 998244353
const int phi = 1e9+6; // 1e9+6, 998244352
// BEFORE coding are you sure you understood the statement correctly?
// PLEASE do not forget to read the sample explanation carefully.
// WATCH out for overflows & RTs in general.
// TEST your idea or code on the corner cases.
// ANALYZE each idea you have thoroughly.

const int N = 1e6+10;
int mx[N];
vector <pair<int, int>> fs[N];
void pre() {
    for (int i = 2; i < N; i++) {
        if (!fs[i].empty()) continue;
        for (int j = i; j < N; j+=i) {
            ll cur = j;
            if (cur%(1LL*i*i) == 0) continue;
            for (int f = 1; cur < N; f++, cur*=i) {
                fs[cur].emplace_back(i, f);
            }
        }
    }
}

void burn(int tc) {
    int n; cin >> n;
    vector <int> a(n);
    int id = 0;
    map <int, int> comp;
    for (auto &i : a) {
        cin >> i;
        for (auto &[p, pw] : fs[i]) {
            mx[p] = max(mx[p], pw);
            if (comp.count(p)) continue;
            comp[p] = id++;
        }
    }


    set <int> b;
    for (auto &i : a) {
        int nw = 1;
        for (auto &[p, pw] : fs[i]) {
            if (mx[p] == pw) nw*=p;
        }
        if (nw > 1) b.insert(nw);
    }
    if (b.empty()) return void (cout << 1);

    set <int> remove;
    for (auto it = b.begin(); it != b.end(); it++) {
        vector <int> divs{1};
        for (auto &[p, dum] : fs[*it]) {
            assert(dum == 1);
            int sz = (int)divs.size();
            for (int i = 0; i < sz; i++) {
                if (p*divs[i] == *it) continue;
                divs.push_back(p*divs[i]);
                if (b.count(divs.back())) remove.insert(divs.back());
            }
        }
    }
    for (auto &i : remove) b.erase(i);

    vector <int> dp(1<<id, 2e9);
    dp[0] = 0;
    for (auto &i : b) {
        int added = 0;
        for (auto &[p, dum] : fs[i]) {
            added|=1<<comp[p];
        }
        for (int msk = (1<<id)-1; ~msk; msk--) {
            int nmsk = msk|added;
            dp[nmsk] = min(dp[nmsk], 1+dp[msk]);
        }
    }
    cout << dp[(1<<id)-1];
}

int main()
{
    AboTaha_on_da_code

//    freopen("cheat.in", "r", stdin);
//    freopen("output.txt", "w", stdout);

    int T = 1; cin >> T;

    pre();

    for (int i = 1; i <= T; i++) {
//        cout << "Case " << i << ": ";
        burn(i);
        cout << '\n';
    }
    return (0-0);
}