#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define sz(s) (int)(s).size()
#define all(s) s.begin(),s.end()

void Speed() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e6 + 5;
int spf[N], need[N], dis[N], vis[N], vid;
void solve() {
    int n; cin >> n;
    vector<vector<array<int, 2>>> a(n);
    map<int, int> mp;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        while(x > 1){
            int p = spf[x]; x /= p;
            if(a[i].empty() || a[i].back()[0] != p) a[i].push_back({p, 1});
            else a[i].back()[1]++;
        }
        for(auto& [p, f] : a[i]){
            if(mp.count(p)) mp[p] = max(mp[p], f);
            else mp[p] = x;
        }
    }

    vector<array<int, 2>> primes;
    for(auto& [p, f] : mp) primes.push_back({p, f});
    vector<int> masks;
    for(auto& v :a){
        int p1 = 0, p2 = 0, cur_mask = 0;
        while(p1 < sz(v)){
            assert(p2 < sz(primes));
            if(v[p1][0] > primes[p2][0]){
                p2++; continue;
            }
            if(v[p1][1] == primes[p2][1]) cur_mask |= (1<<p2);
            p1++; p2++;
        }
        if(cur_mask > 0) masks.push_back(cur_mask);
    }
    if(masks.empty()) return cout << "1\n", void();
    sort(all(masks));
    vector<vector<int>> bit_masks(sz(primes));
    int last = -1;
    for(int x : masks){
        if(x == last) continue;
        last = x;
        for(int b = 0; b < sz(primes); b++){
            if((x >> b) & 1){
                bit_masks[b].push_back(x);
            }
        }
    }

    queue<int> q;
    vid++; q.push(0);
    dis[0] = 0; vis[0] = vid;
    while(!q.empty()){
        int u = q.front(); q.pop();
        int b = sz(primes) - 1;
        while(b >= 0 && ((u >> b) & 1)) b--;
        if(b == -1) return cout << dis[u] << '\n', void();
        for(int x : bit_masks[b]){
            int y = (u | x);
            if(vis[y] == vid) continue;
            vis[y] = vid; dis[y] = dis[u] + 1;
            q.push(y);
        }
    }
    assert(0);
}

int main() {
    for(int i = 2; i < N; i++){
        if(spf[i]) continue;
        for(int j = i; j < N; j += i){
            if(spf[j]) continue;
            spf[j] = i;
        }
    }
    Speed();
    int tc = 1;
    cin >> tc;
    while (tc--) {
        solve();
    }
    return 0;
}