source_code: import java.util.*;
  import java.io.*;
  
  public class Solve{
      public static void main(String[] args) throws Exception{
          Scanner sc=new Scanner(System.in);
          PrintWriter out =new PrintWriter(System.out);
          int size=(int)1e7+1;
          int[] pr=new int[size];
          for(int i=0;i<size;i++){
              pr[i]=i;
          }
          for(int i=2;i*i<size;i++){
             if(pr[i]==i){int val=i*i;
              for(int j=val;j<=size;j+=val){
                   pr[j]=j/val;
              }
             }
          }
          int t=sc.nextInt();
          int[] dp=new int[size];
          Arrays.fill(dp,-1);
          while(t-->0){
              int n=sc.nextInt();
              int k=sc.nextInt();
              int[] ar=new int[n];
              for(int i=0;i<n;i++){
                  int a=sc.nextInt();
                  ar[i]=pr[a];
              }
              int[] ans=new int[k+1];
              int[] ind=new int[k+1];
              for(int i=0;i<n;i++){
                  for(int h=k;h>=0;h--){
                      if(dp[ar[i]]>=ind[h]){
                          ans[h]++;
                          ind[h]=i;
                      }
                      if(h>0 && (ans[h-1]<ans[h] ||(ans[h-1]==ans[h] && ind[h-1]>ind[h])))
                      {
                          ans[h]=ans[h-1];
                          ind[h]=ind[h-1];
                      }
                  }
                  dp[ar[i]]=i;
              }
              out.println(ans[k]+1);
              for(int i=0;i<n;i++)dp[ar[i]]=-1;
          }
          out.close();
      }
  }