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.math.BigInteger;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class e1497 implements Runnable{
	

    static int spf[];
    static void sieve()  { 
        spf[1] = 1; 
        for (int i=2; i<spf.length; i++) 
            spf[i] = i; 
       
        for (int i=4; i<spf.length; i+=2) 
            spf[i] = 2; 
       
        for (int i=3; i*i<spf.length; i++) { 
            if (spf[i] == i) { 
                for (int j=i*i; j<spf.length; j+=i) 
                    if (spf[j]==j) 
                        spf[j] = i; 
            } 
        } 
    } 
    
    static long getFactorization(int x) { 
        long prod = 1;
        Set<Integer> seen = new HashSet<>();
        while (x != 1) 
        { 
            if(seen.contains(spf[x])) {
            	prod /= spf[x];
            	seen.remove(spf[x]);
            } else {
            	prod *= spf[x];
            	seen.add(spf[x]);
            }
            x /= spf[x]; 
        } 
        return prod; 
    } 
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new e1497(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		spf = new int[10000001];
		sieve();
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		int t = scan.nextInt();
		//int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {
		static final int oo = Integer.MAX_VALUE;
		static final long OO = Long.MAX_VALUE;

		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			int K = sc.nextInt();
			
			int[] arr = sc.readArray(N);
			long[] factor = new long[N];
			for(int i = 0; i < N; i++) {
				factor[i] = getFactorization(arr[i]);
			}
			
			Set<Long> cont = new HashSet<>();
			int flag = 1;
			for(int i = 0; i < N; i++) {
				if(cont.contains(factor[i])) {
					flag++;
					cont.clear();
				}
				cont.add(factor[i]);
			}
			
			out.println(flag);
		}
		
		
	}
	static long modInverse(long N, long MOD) {
		return binpow(N, MOD - 2, MOD);
	}
	static long modDivide(long a, long b, long MOD) {
		a %= MOD;
		return (binpow(b, MOD-2, MOD) * a) % MOD;
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static int[] reverse(int a[]) 
    { 
        int[] b = new int[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	static long[] reverse(long a[]) 
    { 
        long[] b = new long[a.length]; 
        for (int i = 0, j = a.length; i < a.length; i++, j--) { 
            b[j - 1] = a[i]; 
        } 
        
        return b;
    }
	
	static void shuffle(Object[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			Object temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}
	static void shuffle(long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}
	
	static class tup implements Comparable<tup>, Comparator<tup>{
		int a, b;
		tup(int a,int b){
			this.a=a;
			this.b=b;
		}
		public tup() {
		}
		@Override
		public int compareTo(tup o){
			return Integer.compare(b,o.b);
		}
		@Override
		public int compare(tup o1, tup o2) {
			return Integer.compare(o1.b, o2.b);
		}
		
		@Override
	    public int hashCode() {
			return Objects.hash(a, b);
	    }
 
	    @Override
	    public boolean equals(Object obj) {
	    	if (this == obj)
                return true;
	    	if (obj == null)
                return false;
	    	if (getClass() != obj.getClass())
                return false;
	    	tup other = (tup) obj;
	    	return a==other.a && b==other.b;
	    }
	    
	    @Override
	    public String toString() {
	    	return a + " " + b;
	    }
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

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

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
		
		int[] readArray(int size) {
			int[] a = new int[size];
			for(int i = 0; i < size; i++) {
				a[i] = nextInt();
			}
			return a;
		}
		
		long[] readLongArray(int size) {
			long[] a = new long[size];
			for(int i = 0; i < size; i++) {
				a[i] = nextLong();
			}
			return a;
		}
	}
	
	static void dbg(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(long[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	static void dbg(boolean[] arr) {
		System.out.println(Arrays.toString(arr));
	}

	static void dbg(Object... args) {
        for (Object arg : args)
            System.out.print(arg + " ");
        System.out.println();
    }
}