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.util.*;
import java.io.*;
//import java.math.*;

public class Task{
        //  ..............code begins here..............

static long mod=(long)1e9+7,inf=(long)1e18;
static int[] spf;
static void spf(int n){
        for(int i=2;i<=(int)Math.sqrt(n);i++){
          if(spf[i]!=0) continue;
          spf[i]=i;
          for(int j=i*i;j<=n;j+=i){
            if(spf[j]!=0) continue;
            spf[j]=i;
          }
        }
        for(int i=(int)Math.sqrt(n);i<=n;i++){
          if(spf[i]==0) spf[i]=i;
        }
}
static void solve() throws IOException {
            int[] x=int_arr();
            int n=x[0],k=x[1];
            int[] a=int_arr();
            Map<List<Integer>,Integer> map=new HashMap<>();
            int res=0;
            for(int i=0;i<n;i++){
                List<Integer> l=new ArrayList<>();
                int tmp=a[i];
                while(tmp>1){
                    int f=spf[tmp],c=0;
                    while(tmp%f==0){
                        c++;tmp/=f;
                    }
                    if(c%2==1)l.add(f);
                }
                Collections.sort(l);
                if(map.get(l)==null) map.put(l,1);
                else{
                    res++;
                    map.clear();map.put(l,1);
                }
            }
            res++;
            out.write(res+"\n");
}
//
public static void main(String[] args) throws  IOException{
                assign();
                int t=int_v(read());
                spf=new int[10000000];
                spf(10000000-1);
                //for(int i=2;i<=500;i++) out.write(spf[i]+", ");
                while(t--!=0){
                    //out.write("Case #"+cn+": ");
                    solve();
                }
                out.flush();
}

// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static void sort(int[] a){List<Integer> l=new ArrayList<>();for(int x:a){l.add(x);}Collections.sort(l);for(int i=0;i<a.length;i++){a[i]=l.get(i);}}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
//static String setpreciosion(double d,int k){BigDecimal d1 = new BigDecimal(Double.toString(d));return d1.setScale(k,RoundingMode.HALF_UP).toString();}//UP DOWN HALF_UP
static int add(int a,int b){int z=a+b;if(z>=mod)z-=mod;return z;}
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
static long Modpow(long a,long p,long m){long res=1;while(p>0){if((p&1)!=0){res=(res*a)%m;}p >>=1;a=(a*a)%m;}return res%m;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
//static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
//static long[] f;
}