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.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class b{ 

     static FastScanner sc;
     static long[] arr;
     static long mul,mul1;
     static int[] spf;
     static int n,q;
     static long mod = ((long)(1e9))+7;

     static long[] st;
    static long[] lazy;

    static void func(int n) {
        st = new long[5 * n];
        lazy = new long[5 * n];
        for (int i = 0; i < 5* n; i++) {
            st[i] = 1;
            lazy[i] = 1;
        }
    }

    static void pushdown(int node, int ss, int se) {
        st[node] *= lazy[node];
        if (ss != se) {
            lazy[2 * node + 1] *= lazy[node];
            lazy[2 * node + 2] *= lazy[node];
        }
        lazy[node] = 1;

    }

    static void update(int node, int ss, int se, int l, int r, int val) {
        pushdown(node, ss, se);
        // break condition
        if (se < l || ss > r) {
            return;
        }
        // tag condition
        if (ss >= l && se <= r) {
            lazy[node] = mod(lazy[node]*val,mod);
            pushdown(node, ss, se);
            return;
        }
        int mid = (ss + se) / 2;
        update(2 * node + 1, ss, mid, l, r, val);
        update(2 * node + 2, mid+1, se, l, r, val);
        st[node] = combine(st[2 * node + 1], st[2 * node + 2]);
    }

    static long combine(long a, long b) {
        if (b == 0) {
            return a;
        }
        return combine(b, a % b);
    }

    static long get(int node, int ss, int se, int l, int r) {
        pushdown(node, ss, se);
        if (se < l || ss > r) {
            return 1;
        }
        if (ss >= l && se <= r) {

            return st[node];
        }
        int mid = (ss + se) / 2;
        if(mid<l){
            return get(2*node+2, mid+1, se, l, r);
        }else if(mid+1>r){
            return get(2*node+1, ss, mid, l, r);
        }
        return combine(get(2 * node + 1, ss, mid, l, r), get(2 * node + 2, mid + 1, se, l, r));
    }

    public static void SpecialSieve(int MAXN) 
    {   

        spf = new int[MAXN];
        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 (int i=3; i*i<MAXN; i++) 
        { 
            // checking if i is prime 
            if (spf[i] == i) 
            { 
                // marking SPF for all numbers divisible by i 
                for (int j=i*i; j<MAXN; j+=i) 
       
                    // marking spf[j] if it is not  
                    // previously marked 
                    if (spf[j]==j) 
                        spf[j] = i; 
            } 
        } 
    } 

    public static void getFactorization(int x) 
    { 
        // ArrayList<Integer> ret = new ArrayList<Integer>(); 
        mul = 1;
        mul1 = 1;
        int curr = 0;
        while (x != 1) 
        {      
            // System.out.println(spf[x]);
            int num = spf[x];
            // ret.add(num); 
            while(x%num == 0){
                x /= num;
                curr += 1;
            }
            if(curr%2 == 0)
                mul1 *= num;
            else
                mul *= num;
            curr = 0;
        } 
        // System.out.println(mul + " " + mul1);
        // System.out.println(mul);
    } 

     public static void solve(){

        int ans = 1;
        Set<Long> set = new HashSet<>();

        for(int k = 0 ; k < n ; k++){

            getFactorization((int)arr[k]);
            if(set.contains(mul)){
                ans += 1;
                set = new HashSet<>();
            }
            set.add(mul);
            if(mul == 1){
                set.add(mul1*mul1);
            }
            // System.out.println(mul);
        }

        System.out.println(ans);

     }

        
     public static void main(String[] args) {

            sc = new FastScanner();
            // Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            SpecialSieve((int)(1e7)+1);
            // int t = 1;
            while(t > 0){

                n = sc.nextInt();
                q = sc.nextInt();
                arr = new long[n];
                for(int i = 0 ; i < n ; i++)
                    arr[i] = sc.nextLong();
                solve();       
                t -= 1;
            }

     }

    // Use this instead of Arrays.sort() on an array of ints. Arrays.sort() is n^2
    // worst case since it uses a version of quicksort. Although this would never
    // actually show up in the real world, in codeforces, people can hack, so
    // this is needed.
    static void ruffleSort(int[] a) {
        //ruffle
        int n=a.length;
        Random r=new Random();
        for (int i=0; i<a.length; i++) {
            int oi=r.nextInt(n), temp=a[i];
            a[i]=a[oi];
            a[oi]=temp;
        }
        
        //then sort
        Arrays.sort(a);
    }
    public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b); 
    }
    public static long mod(long x, long mod)
{
    long result = x % mod;
    if (result < 0)
    {
        result += mod;
    }
    return result;
}
    
    // Use this to input code since it is faster than a Scanner
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        String next() {
            while (!st.hasMoreTokens())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
        int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
        long nextLong() {
            return Long.parseLong(next());
        }
    }
}
 