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] 
// Don't place your source in a package
import java.text.DecimalFormat;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;








// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {//scanner from SecondThread
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(System.out);
        List<Integer>primes=new ArrayList<>();
        int p[]=new int[10000];
        for(int i=2;i<p.length;i++){
            if(p[i]!=0)continue;
            primes.add(i);
            for(int j=i;j<p.length;j+=i){
                p[j]=1;
            }
        }


        int T=Int();
        for(int t=0;t<T;t++){
            int n=Int();
            int k=Int();
            int A[]=new int[n];
            for(int i=0;i<n;i++){
                A[i]=Int();
            }

            Sol sol=new Sol();
            sol.solution(out,A,k,primes);
        }
        out.flush();

    }

    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}



class Sol{

    public void solution(PrintWriter out,int A[],int k,List<Integer>primes){
        int res=0;
        int n=A.length;
        int match[]=new int[n];
        Arrays.fill(match,n);
        Map<String,Integer>f=new HashMap<>();
        for(int i=0;i<A.length;i++){
            String s=hash(A[i],primes);
            if(f.containsKey(s)){
                int index=f.get(s);
                match[index]=i;
                f.put(s,i);
            }
            else{
                f.put(s,i);
            }
        }

        //greedy take
        for(int i=0;i<n;i++){
            int end=match[i];
            int j=i;
            res++;
            while(j<end){
                end=Math.min(end,match[j]);
                j++;
            }
            i=j-1;
        }
        out.println(res);
    }

    public String hash(int n,List<Integer>primes){
        StringBuilder str=new StringBuilder("x,");
        for(int i:primes){
            if(i*i>n)break;
            int cnt=0;
            while(n%i==0){
                n/=i;
                cnt++;
            }
            cnt%=2;
            if(cnt!=0)str.append(i+",");
        }
        if(n!=1)str.append(n+",");
        return str.toString();

    }

}
//42



