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.awt.*;
import java.io.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;

public class Main {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;

        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
//
//

    //    static class TreeNode {
//        int val;
//        TreeNode left,right;
//        TreeNode(int val){
//            this.val=val;left=null;right=null;
//        }
//    }
//    static TreeNode maxx(int start,int end,int[] arr){
//        if(start>end){
//            return null;
//        }
//        int ind=0;
//        int max=-1;
//        for(int j=start;j<=end;j++){
//            if(arr[j]>max){
//                max=arr[j];
//                ind=j;
//            }
//        }
//        TreeNode jj=new TreeNode(arr[ind]);
//        jj.left=maxx(start,ind-1,arr);
//        jj.right=maxx(ind+1,end,arr);
//        return jj;
//
//    }
//    static void dfs(TreeNode root,int dep){
//        if(root==null){
//            return;
//        }
//        ans[hashMap.get(root.val)]=dep;
//        dfs(root.left,dep+1);
//        dfs(root.right,dep+1);
//    }
//    static int[] ans;
//   static HashMap<Integer,Integer> hashMap;
//   static class pont{
//       int val,index;
//       pont(int val,int index){
//           this.val=val;
//           this.index=index;
//       }
//   }
//   static class compr implements Comparator<pont>{
//       public int compare(pont a,pont b){
//           return a.val-b.val;
//       }
//   }
//    static class poin{
//       int src;
//       long val;
//       poin(int src,long val){
//           this.src=src;
//           this.val=val;
//       }
//    }
//
//    static double maxx(int flag,String s,String t,int k){
//
//       if(flag==0){
//
//           StringBuilder stringBuilder = new StringBuilder(s.substring(0,s.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//
//               ans=(double)((double)ans+(double)maxx(1,str.toString(),t,k));
//           }
//           return ans;
//       }
//       else if(flag==1){
//
//           StringBuilder stringBuilder = new StringBuilder(t.substring(0,t.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//               ans=(double)((double)ans+(double)maxx(2,s,str.toString(),k));
//           }
//           return ans;
//
//       }
//       else{
//           long[] count=new long[10];
//           long taka=0;
//           long[] tot=new long[10];
//
//           for(int j=0;j<s.length();j++){
//               int a=Integer.parseInt(String.valueOf(s.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               taka=(long)((long)taka+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           long aoki=0;
//           count=new long[10];
//           for(int j=0;j<t.length();j++){
//               int a=Integer.parseInt(String.valueOf(t.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               aoki=(long)((long)aoki+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           if(aoki>=taka){
//               return 0;
//           }else{
//               if(t.charAt(t.length()-1)==s.charAt(s.length()-1)){
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)2;
//                   return (double)((double)((double)(kk)*(double)(kk-(double)1))/(double)((double)1*((double)9*(double)k-(double)8)*(double)((double)9*(double)k-(double)9)));
//
//               }else{
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)1;
//                   double kk2=(double)k-(double)tot[Integer.parseInt(String.valueOf(s.charAt(s.length()-1)))]+(double)1;
//                   return (double)(((double)((double)1*(double)kk)*(double)(kk2))/(double)((double)1*((double)9*(double)k-(double)8)*(double) ((double)9*(double)k-(double)9)));
//               }
//           }
//
//       }
//
//
//    }
//
//   static void sieveOfEratosthenes(int n)
//    {
//        boolean prime[] = new boolean[n + 1];
//        for (int i = 0; i <= n; i++)
//            prime[i] = true;
//
//        for (int p = 2; p * p <= n; p++)
//        {
//            if (prime[p] == true)
//            {
//                for (int i = p * p; i <= n; i += p)
//                    prime[i] = false;
//            }
//        }
//
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                treeMap.put(i,0);
//        }
//    }
//    static TreeMap<Integer,Integer> treeMap;
    static class comp implements Comparator<Point> {
        public int compare(Point a,Point b){
            if(b.y==a.y){
                return a.x-b.x;
            }
            return b.y-a.y;
        }
    }
    static boolean ff=false;

    static void maxx(int ind,int l,int r,int d,int u,int n)
    {
        if(ind==4){
            if(l<0 || r<0 || u<0 || d<0){
                return;
            }
            ff=true;
            return;
        }
        if(ind==0){
            if(l==n){
                maxx(ind+1,l-2,r,d-1,u-1,n);
            }else if(l==n-1){
                maxx(ind+1,l-1,r,d-1,u,n);
                if(ff){
                    return;
                }
                maxx(ind+1,l-1,r,d,u-1,n);
            }else{
                maxx(ind+1,l,r,d,u,n);
            }

        }else if(ind==1){
            if(r==n){
                maxx(ind+1,l,r-2,d-1,u-1,n);
            }else if(r==n-1){
                maxx(ind+1,l,r-1,d-1,u,n);
                if(ff){
                    return;
                }
                maxx(ind+1,l,r-1,d,u-1,n);
            }else{
                maxx(ind+1,l,r,d,u,n);
            }

        }else if(ind==2){
            if(d==n){
                maxx(ind+1,l-1,r-1,d-2,u,n);
            }else if(d==n-1){
                maxx(ind+1,l-1,r,d-1,u,n);
                if(ff){
                    return;
                }
                maxx(ind+1,l,r-1,d-1,u,n);
            }else{
                maxx(ind+1,l,r,d,u,n);
            }

        }else{
            if(u==n){
                maxx(ind+1,l-1,r-1,d,u-2,n);
            }else if(u==n-1){
                maxx(ind+1,l-1,r,d,u-1,n);
                if(ff){
                    return;
                }
                maxx(ind+1,l,r-1,d,u-1,n);
            }else{
                maxx(ind+1,l,r,d,u,n);
            }
        }
    }
    static void filereader() throws IOException{
        FileReader fileReader=new FileReader("input.txt");
        int ch;
        String str="";
        StringBuilder stringBuilder=new StringBuilder();
        while ((ch=fileReader.read())!=-1)
            stringBuilder.append((char)ch);

        fileReader.close();
        StringBuilder ans=new StringBuilder();
        FileWriter fw=new FileWriter("output.txt");
        for(int j=0;j<ans.length();j++){
            fw.write(ans.charAt(j));
        }
        fw.close();
    }
    static class point{
        int w,v;
        point(int v,int w){
            this.v=v;
            this.w=w;
        }
    }
    static class compp implements Comparator<point>{
        public int compare(point a,point b){
            return b.v-a.v;
        }
    }

    static int cal(int ind,String s,String x,int val){
        if(ind>=s.length()){
            if(val%7==0){
                return 1;
            }else{
                return 0;
            }
        }
        if(aa[ind][val]!=-1){
            return aa[ind][val];
        }

        if(x.charAt(ind)=='A'){
            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
            return aa[ind][val]=Math.min( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
        }else{
            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
            return aa[ind][val]=Math.max( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
        }

    }
    static int aa[][];

    public static void main(String[] args) throws IOException {

        Reader s=new Reader();
        List<Integer> primes=new ArrayList<>();
        boolean[] prime=new boolean[(int)Math.pow(10,7)+1];
        for(int j=1;j<prime.length;j++){
            prime[j]=true;
        }
        for(int j=2;j*j<prime.length;j++){
            if(!prime[j]){
                continue;
            }
            for(int i=j*j;i<prime.length;i=i+j){
                prime[i]=false;
            }
        }
        for(int j=2;j<prime.length;j++){
            if(prime[j]){
                primes.add(j);
            }
        }

        int t=s.nextInt();
        for(int j=0;j<t;j++){
            int n=s.nextInt();
            int k=s.nextInt();
            HashSet<Integer> has=new HashSet<>();
            int an=1;
            for(int i=0;i<n;i++){
                int temp=s.nextInt();
                int prod=1;
                for(Integer prim:primes){
                    if(prim>Math.sqrt(temp)){
                        break;
                    }
                    int co=0;
                    while(temp%prim==0){
                        co++;
                        temp/=prim;
                    }
                    co=co%2;
                    if(co==1){
                        prod=prod*prim;
                    }
                }
                if(temp>1){
                    prod=prod*temp;
                }
                if(has.contains(prod)){
                    an++;
                    has=new HashSet<>();

                }
                has.add(prod);

            }
            System.out.println(an);



        }


}
}







