#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n,m;
    cin>>n>>m;
    set<int> s;
    int ok=1;
    for (int i=0,x;i<n;i++){
        cin>>x;
        map<int,int> m;
        for (int j=2;j*j<=x;j++){
            while (x%j==0)
            {
                m[j]++;
                x/=j;
            }
        }
        if (x!=1){m[x]++;}
        //for (auto it:m){cout<<it.first<<" "<<it.second<<"\n";}
        //cout<<endl;
        int ans=1;
        vector<pair<int,int>> v;
        for (auto it:m){
            int k=it.first,k1=it.second;
            for (int j=1;j<32;j++){
                if (k1<=(1<<j)){
                    //cerr<<(1<<j)<<endl;
                    int z=(1<<j)-k1;
                    while (z--)
                    {
                        ans*=k;
                    }
                    break;
                }
            }
        }
        //cerr<<ans<<" ans\n";
        if (ans!=0){
            if (s.find(ans)==s.end()){
                s.insert(ans);
            }
            else{
                ok++;
                s.clear();
                s.insert(ans);
            }
        }
    }
    cout<<max(ok,1)<<"\n";
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc=1;
    cin>>tc;
    for (;tc;tc--){solve();}
}