/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
*/
/*
  Credits -
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/ (namespace atcoder)
  Github source code of library - https://github.com/atcoder/ac-library/tree/master/atcoder
  https://codeforces.com/contest/4/submission/150120627
*/
 
#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
    #pragma GCC optimize ("-ffloat-store")
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #define dbg(args...) 42;
    #define endl "\n"
#endif
 
// y_combinator from @neal template https://codeforces.com/contest/1553/submission/123849801
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
 
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
 
typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;
template <class T>
using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
// X.find_by_order(k) return kth element. 0 indexed.
// X.order_of_key(k) returns count of elements strictly less than k.
 
const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}
 
const lli INF = 0xFFFFFFFFFFFFFFFLL;
const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(SEED);
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}
 
class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};
 
void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}
 
void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}
 
bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}
 
const lli C = 1e8,CSq = (lli)sqrt(C)+5;
const int BITS = 1250;// no of primes upto CSq;
using bt = bitset<BITS>;
const bt ZERO;
bt min(bt a,bt b){
    const lli f=(a^b)._Find_first();
    return (a[f]?b:a);
}
bt max(bt a,bt b){
    return a^b^min(a,b);
}
 
struct Gauss
{
    int bits = BITS;
    vector<bt> table;
 
    Gauss()
    {
        table = vector<bt> (bits, ZERO);
    }
 
    Gauss(int _bits)
    {
        bits = _bits;
        table = vector<bt> (bits, ZERO);
    }
 
    int size()
    {
        int ans = 0;
        for(int i = 0; i < bits; i++)
        {
            if(table[i] != ZERO)
                ans++;
        }
        return ans;
    }
 
    bool can(bt x)
    {
        for(int i = bits - 1; i >= 0; i--)
            x = min(x, x ^ table[i]);
        return x == ZERO;
    }
 
    void add(bt x)
    {
        for(int i = bits - 1; i >= 0 && x != ZERO; i--)
        {
            if(table[i] == ZERO)
            {
                table[i] = x;
                x = ZERO;
            }
            else
                x = min(x, x ^ table[i]);
        }
    }
 
    bt getBest()
    {
        bt x = ZERO;
        for(int i = bits - 1; i >= 0; i--)
            x = max(x, x ^ table[i]);
        return x;
    }
 
    void merge(Gauss &other)
    {
        for(int i = bits - 1; i >= 0; i--)
            add(other.table[i]);
    }
};
 
 
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
 
vector<bool> vis(CSq+1,false);
vi primes;
for(lli p=2;p*p<=C;p++){
    if(vis[p])
        continue;
    primes.pb(p);
    for(lli j=p*p;j*j<=C;j+=p)
        vis[j]=true;
}
const lli N = sz(primes);
assert(N<=BITS);
lli T;
cin>>T;while(T--)
{
 
    lli n;
    cin>>n;
 
    auto getRank=[&](const set<lli> b)->lli{
        Gauss g;
        for(auto cur:b){
            bt curBt;
            for(lli i=0;i<N;++i)
            {
                const lli p=primes[i];
                if(cur%p)
                    continue;
                lli c=0;
                while(cur%p==0){
                    c^=1;
                    cur/=p;
                }
                curBt[i]=c;
            }
            g.add(curBt);
        }
        return g.size();
    };
 
    auto normalize=[&](lli cur)->ii{
        lli no=1;
        for(auto p:primes){
            if(cur%p)
                continue;
            lli c=0;
            while(cur%p==0){
                c^=1;
                cur/=p;
            }
            if(c)
                no*=p;
        }
        return {no,cur};
    };
 
    map<lli,lli> oth;
    set<lli> b;
    for(lli i=0;i<n;++i){
        lli cur,no=1;
        cin>>cur;
        tie(no,cur)=normalize(cur);
        if(cur>1){
            if(oth.count(cur)){
                cur=no*oth[cur];
                tie(no,cur)=normalize(cur);
                assert(cur==1);
            }
            else{
                oth[cur]=no;
                continue;
            }
        }
        if(no==1)
            continue;
        if(b.count(no))
            continue;
        b.insert(no);
    }
 
    cout<<sz(oth)+getRank(b)<<endl;
 
}   aryanc403();
    return 0;
}