#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<map>
#include<iostream>
#include<cstring>
using namespace std;
template<class _T>inline void read(_T &_a)
{
    bool f=0; char _c=getchar(); _a=0;
    while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
    while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
    if(f) _a=-_a;
}

const long long MAXN=10000000;
long long pri[MAXN],pricnt;
bool npri[MAXN+1];
int n,T,a[200010],k,ans;
map<int,bool>vis;

inline void init()
{
    for (long long i=2;i<=MAXN;++i)
    {
        if(!npri[i]) pri[++pricnt]=i;
        for (int j=1;j<=pricnt&&i*pri[j]<=MAXN;++j)
        {
            npri[i*pri[j]] = true;
            if(i%pri[j]==0) break;
        }
    }
}

int main()
{
    init();
    for(read(T);T;--T)
    {
        ans=0;
        vis.clear();
        read(n);
        read(k);
        for (int i=1;i<=n;++i)
        {
            read(a[i]);
            for (int j=1;j<=pricnt&&pri[j]*pri[j]<=a[i];++j)
                while(a[i]%(pri[j]*pri[j])==0)
                    a[i]/=pri[j]*pri[j];
            //printf("[%d]",a[i]);
        }
        for (int i=1;i<=n;++i)
        {
            if(vis[a[i]])
            {
                ++ans;
                vis.clear();
            }
            vis[a[i]]=true;
        }
        printf("%d\n",ans+1);
    }

    return 0;
}