#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[10000001];
void fun()
{  int i,n=10000001,j;
     for(i=0;i<n;i++)
        a[i]=i;
      for(i=2;i*i<n;i++)
     {   if(a[i]==i)
          { for(j=i*i;j<n;j+=i)
               a[j]=i;
          }
     }
}
int main(){
    fun();
   int t;
    cin>>t;
     while(t--)
    {  int n,k,i,f=0,x,c=1;
         cin>>n>>k;
        int b[n];
         for(i=0;i<n;i++)
            cin>>b[i];
            unordered_set<int>s;
         for(i=0;i<n;i++)
         {   f=0;
             unordered_map<int,int>m;
                x=b[i];
               while(x!=1)
                 {   m[a[x]]++;
                     x/=a[x];
                 }
                 x=1;
                 for(auto it=m.begin();it!=m.end();it++)
                 {    if(it->second%2)
                       x=x*it->first;
                 }
               //  cout<<x<<" ";
                 if(s.find(x)!=s.end())
                 { c++;
                     s.clear();
                 }
                  s.insert(x);
         }
         cout<<c<<endl;
    }
}
