This is the easy version of the problem. The only difference is that in this version k = 0.

There is an array a_1, a_2, …, a_n of n positive integers. You should divide it into a minimal number of continuous segments, such that in each segment there are no two numbers (on different positions), whose product is a perfect square.

Moreover, it is allowed to do at most k such operations before the division: choose a number in the array and change its value to any positive integer. But in this version k = 0, so it is not important.

What is the minimum number of continuous segments you should use if you will make changes optimally?

Input

The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases.

The first line of each test case contains two integers n, k (1 ≤ n ≤ 2 ⋅ 10^5, k = 0).

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7).

It's guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case print a single integer — the answer to the problem.

Example

Input


3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1


Output


3
2
1

Note

In the first test case the division may be as follows:

  * [18, 6] 
  * [2, 4] 
  * [1] 
import java.io.*;
import java.util.*;
import java.math.BigInteger; 

public class test1 {
    
    
   static class sort implements Comparator<int[]>
   {
        public int compare(int[] a,int[] b)
        {
            //if(a[0] == b[0]) return a[1]-b[1];
           return a[0]-b[0];
        }
   }
   public static void pr(PrintWriter out,Object o)
   {
      
    out.println(o.toString());out.flush();
    
   }
   public static void prW(PrintWriter out,Object o)
   {
      
    out.print(o.toString());out.flush();
    
   }
   public static int intIn(String st)
   {
      return Integer.parseInt(st);
   }
   
   
    
    public static void pr(Object o)
    {
        System.out.println(o.toString());
    }
    public static void prW(Object o)
    {
        System.out.print(o.toString());
    }
    
   
    public static int inInt(String s)
    {
        return Integer.parseInt(s);
    }
    public static long in(String s)
    {
        return Long.parseLong(s);
    }

    
    
    static int[] toIntArray(String[] m) 
    { 
        int[] p=new int[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= inInt(m[o]);
        }
        return p;
    }
    static long[] toLArray(String[] m) 
    { 
       long[] p=new long[m.length];
        for(int o=0;o<m.length;o++)
        {
            p[o]= in(m[o]);
        }
        return p;
    }
    static long max=10000000000000l;static int[] before;static int R;
    
    public static String[] F(BufferedReader bf) throws Exception
    {
        return (bf.readLine().split(" "));
    }
    static long res=0l;
    public static int F(int i,int p,Integer[][] dp,char[] a,char[] b)
    {
       if(i>=a.length)
       {
          if(p==0) return 0;return -100000000;
       }

       if(dp[i][p] != null)  return dp[i][p];
       int res=0;
       if(a[i] == b[i])
       {
            if(p>0) res = F(i+1,p-1,dp,a,b)+1;
            res=Math.max(res,F(i+1,p,dp,a,b));
       }
       else
       {
            if(p>0) res = F(i+1,p-1,dp,a,b);
            res=Math.max(res,F(i+1,p,dp,a,b)+1);
       
       }

       dp[i][p]=res;return res;

    }
    public static int F(int i,int p,int u,Integer[][][] dp,char[] a,char[] b,char[] c)
    {
       if(i>=a.length)
       {
          if(p==0 && u==0) return 0;return -100000000;
       }

       if(dp[i][p][u] != null)  return dp[i][p][u];
       int res=0;
       if(a[i] == b[i] && b[i]==c[i])
       {
            if(p>0 && u>0) res = F(i+1,p-1,u-1,dp,a,b,c)+1;
            res=Math.max(res,F(i+1,p,u,dp,a,b,c));
       }
       else if(a[i]==c[i])
       {
            if(p>0) res = F(i+1,p-1,u,dp,a,b,c)+1;
            if(u>0)
            res=Math.max(res,F(i+1,p,u-1,dp,a,b,c));
       }
       else if(b[i]==c[i])
       {
            if(u>0) res = F(i+1,p,u-1,dp,a,b,c)+1;
            if(p>0)
            res=Math.max(res,F(i+1,p-1,u,dp,a,b,c));
       }
       else if(a[i]==b[i])
       {
            if(p>0 && u>0) res = F(i+1,p-1,u-1,dp,a,b,c);
            res=Math.max(res,F(i+1,p,u,dp,a,b,c)+1);
       }

       dp[i][p][u]=res;return res;

    }
    
    static final int MAXN = 10000001; 
       
    // stores smallest prime factor for every number 
    static int spf[] = new int[MAXN]; 
       
    // Calculating SPF (Smallest Prime Factor) for every 
    // number till MAXN. 
    // Time Complexity : O(nloglogn) 
    static void sieve() 
    { 
        spf[1] = 1; 
        for (int i=2; i<MAXN; i++) 
       
            // marking smallest prime factor for every 
            // number to be itself. 
            spf[i] = i; 
       
        // separately marking spf for every even 
        // number as 2 
        for (int i=4; i<MAXN; i+=2) 
            spf[i] = 2; 
       
        for (long i=3l; i*i<MAXN; i++) 
        { 
            // checking if i is prime 
            int ip = (int)(i);
            if (spf[ip] == ip) 
            { 
                // marking SPF for all numbers divisible by i 
                for (long j=i*i; j<MAXN; j+=i) {

                    int jp = (int)(j);
                    // marking spf[j] if it is not  
                    // previously marked 
                    if (spf[jp]==jp) 
                        spf[jp] = ip; }
            } 
        } 
    } 
       
    // A O(log n) function returning primefactorization 
    // by dividing by smallest prime factor at every step 
    static long getFactorization(int x) 
    { 
        long res=1l;
        //Vector<Integer> ret = new Vector<>(); 
        int curr=1;int c=0;
        while (x != 1) 
        { 
            if(spf[x] > curr)
            {
                c=(c%2);
                if(c==1) res = (res*(curr+0l));
                curr=spf[x];c=0;
                
            }
           // ret.add(spf[x]); 
            x = x / spf[x];
            c++; 
        }
        c=(c%2);
        if(c==1) res = (res*(curr+0l));

        return res; 
    }
    public static void main (String[] args) throws Exception {
        
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        //PrintWriter out = new PrintWriter(System.out);;;
        
        //int[] map=new int[1000001];
      
        int y=Integer.parseInt(bf.readLine());
        sieve(); 
        for(int w=0;w<y;w++)
        {

            
            
            String[] xlp = bf.readLine().split(" ");;;
            
            int n,k,t,h;//boolean bol=false;
           int m;long a,b,c;
            n=inInt(xlp[0]);//m=in(xlp[1]);//k=inInt(xlp[2]);//t=inInt(xlp[3]);
            int[] arr = toIntArray(F(bf));
            Set<Long> map=new HashSet<>();int ans=1;//boolean col=false;
            
           // char[] ar = new char[up+1];
            
            for(int o=0;o<n;o++)
            {
               // if(arr[0])
                
                
                //ar[0]=ar[1]=0;
                //boolean bol=true;
                long mask = getFactorization(arr[o]); 
                
               //pr(mask);
                if(map.contains(mask))
                {
                   // pr(mask+" "+ans+" "+o);
                    map.clear();ans++;
                }
                else
                {
                    
                }
                map.add(mask);
            }

            pr(ans);
            
            
        }
        //out.close();

    }
}


/*
1
8
13 13 9 12 13 1 13 1

1
5
8 4 7 -2 
1 2
1 3
3 4 
4 5



100663319,201326611,402653189,805306457,1610612741
Kickstart
String rp;
            rp = "Case #"+(w+1)+": "+(n-ans)+" ";
            if(curr == max) rp=rp +"INDEFINITELY";
            else rp = rp+(curr);
static int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};

static class SegmentTreeRMQ 
    { 
    int st[]; 
    int minVal(int x, int y) { 
        return (x > y) ? x : y; 
    } 
  
    
    int getMid(int s, int e) { 
        return s + (e - s) / 2; 
    } 
  
    
    int RMQUtil(int ss, int se, int qs, int qe, int index) 
    { 
        
        if (qs <= ss && qe >= se) 
            return st[index]; 
  
        // If segment of this node is outside the given range 
        if (se < qs || ss > qe) 
            return Integer.MIN_VALUE; 
  
        // If a part of this segment overlaps with the given range 
        int mid = getMid(ss, se); 
        return minVal(RMQUtil(ss, mid, qs, qe, 2 * index + 1), 
                RMQUtil(mid + 1, se, qs, qe, 2 * index + 2)); 
    } 
  
    // Return minimum of elements in range from index qs (query 
    // start) to qe (query end).  It mainly uses RMQUtil() 
    int RMQ(int n, int qs, int qe) 
    { 
        // Check for erroneous input values 
        
  
        return RMQUtil(0, n - 1, qs, qe, 0); 
    } 
  
    // A recursive function that constructs Segment Tree for 
    // array[ss..se]. si is index of current node in segment tree st 
    int constructSTUtil(int arr[], int ss, int se, int si) 
    { 
        // If there is one element in array, store it in current 
        //  node of segment tree and return 
        if (ss == se) { 
            st[si] = arr[ss]; 
            return arr[ss]; 
        } 
  
        // If there are more than one elements, then recur for left and 
        // right subtrees and store the minimum of two values in this node 
        int mid = getMid(ss, se); 
        st[si] = minVal(constructSTUtil(arr, ss, mid, si * 2 + 1), 
                constructSTUtil(arr, mid + 1, se, si * 2 + 2)); 
        return st[si]; 
    } 
  
    
    void con(int arr[]) 
    { 
        // Allocate memory for segment tree 
  
        //Height of segment tree 
        int n = (arr.length);
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
  
        //Maximum size of segment tree 
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
        st = new int[max_size]; // allocate memory 
  
        // Fill the allocated memory st 
        constructSTUtil(arr, 0, n - 1, 0); 
    }
    }
     static class DSU {
    
    int[] p;int[] sz;int op;int c;;
    int[] last;
    public void G(int n)
    {
        last=new int[n];
        p=new int[n];
        sz=new int[n];c=n;
        op=n;
        for(int h=0;h<n;h++)
        {
            sz[h]=1;p[h]=h;
            last[h]=h;
        }
    }
    public int find(int x)
    {
        int y=x;
        while(x!=p[x]) x=p[x];
        while(y!=p[y])
        {
            int tem=p[y];
            p[y]=x;y=tem;
        }
        return p[y];
    }
    public void union(int a,int b)
    {
        int x,y;
        x=find(a);y=find(b);
        if(x==y) return;
        if(sz[x]>sz[y])
        {
            p[y] = x;
            sz[x]+=sz[y];
            last[x]=Math.max(last[x],last[y]);
        }
        else
        {
            p[x]=y;sz[y]+=sz[x];
            last[y]=Math.max(last[y],last[x]);
        }
        c--;
        
    }}

    static long pow(long x, long y, long p)
      {
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0l; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
      static long gcd(long a, long b)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b); 
        }
        static int gcd(int a, int b,int o)
        {
          if (b == 0)
            return a;
          return gcd(b, a % b,o); 
        }


*/