#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef vector< long long > vi;
typedef pair<long long, long long> ii;
typedef priority_queue <ll> pq;
#define o_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
 
const ll mod = 1000000007;
const ll INF = (ll)1e18;
const ll MAXN = 1000006;
 
ll po(ll x, ll n){ 
    ll ans=1;
    while(n>0){ if(n&1) ans=(ans*x)%mod; x=(x*x)%mod; n/=2;}
    return ans;
}
 
const ll MX=32000;
int lp[MX];
vi pr;
const int sz = 3500;
 
void pre(){
    rep_a(i,2,MX){
        if(lp[i]==0){
            lp[i]=i;
            pr.pb(i);
 
        }
        for(int j=0;j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<MX;j++){
            lp[i*pr[j]]=pr[j];
        }
    }
}
 
ii remove_sqs(ll x){
    ii ret = mp(1,1);
    for(auto h:pr){
        if(x%h==0){
            bool par = 0;
            while(x%h==0){
                x/=h;
                par^=1;
            }
            if(par) ret.ff*=h;
        }
    }
    ret.ss=x;
    return ret;
}
 
bitset<sz> get_bits(ll x){
    bitset<sz> ret(0);
    rep(i,pr.size()){
        if(x%pr[i]==0) ret[i]=1;
    }
    return ret;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r" , stdin);
    // freopen("output.txt", "w" , stdout);
    // #endif
    int T=1;
    pre();
    cin >> T;
    while(T--){
        
        int n;
        cin>>n;
 
        vi a(n);
        rep(i,n) cin>>a[i];
 
        map<ll,ll> m;
        vector<bitset<sz> > v(sz,0);
        int rank = 0;
        rep(i,n){
            auto z = remove_sqs(a[i]);
 
            bitset<sz> bt;
            int f = 0;
 
            if(z.ss>1){
                if(m.find(z.ss)==m.end()){
                    m.insert(mp(z.ss, z.ff));
                    rank++;
                    continue;
                }
                else{
                    bitset<sz> tmp = get_bits(z.ff);
                    bt = get_bits(m[z.ss]);
                    bt^=tmp;
                    f=1;
                }
            }
 
            if(!f) bt = get_bits(z.ff);
            rep(j,sz){
                if(bt[j]){
                    if(v[j]==0){
                        v[j]=bt;
                        break;
                    }
                    bt^=v[j];
                }
            }
 
            if(bt!=0) rank++;
        }
 
 
        cout<<rank<<el;
 
    
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}