import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Queue;

public class E3 {
	InputStream is;
	FastWriter out;
	String INPUT = "";
	
	void solve()
	{
		for(int T = ni();T > 0;T--)go();
	}

	int[] lpf = enumLowestPrimeFactors(10000000);

	void go()
	{
		int n = ni(), K = ni();
		int[] a = na(n);
		for(int i = 0;i < n;i++){
			a[i] = factorFast(a[i], lpf);
		}
		a = shrink(a);

		int[][] dp = new int[K+1][n+1];
		for(int i = 0;i <= K;i++){
			Arrays.fill(dp[i], 999999999);
		}
		for(int i = 0;i <= K;i++)dp[i][0] = 0;

		int[] prev = makePrev(a, n+1);

		int[] imos = new int[n+5];
		int[] pp = new int[K+1];
		int[] vs = new int[K+1];
		for(int i = 0;i < n;i++){
			int p = prev[i];
			imos[p+1]--;

			for(int j = 0;j <= K;j++){
				vs[j]++;
				if(pp[j] >= p+1){
					vs[j]--;
				}
				while(vs[j] > j){
					pp[j]++;
					vs[j] += imos[pp[j]];
				}
				for(int k = 0;k+j <= K;k++){
					dp[k+j][i+1] = Math.min(dp[k+j][i+1], dp[k][pp[j]] + 1);
				}
			}
		}
		out.println(dp[K][n]);
	}

	public static int[] shrink(int[] a) {
		int n = a.length;
		long[] b = new long[n];
		for (int i = 0; i < n; i++) b[i] = (long) a[i] << 32 | i;
		Arrays.sort(b);
		int[] ret = new int[n];
		int p = 0;
		for (int i = 0; i < n; i++) {
			if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0) p++;
			ret[(int) b[i]] = p;
		}
		return ret;
	}


	public static int[] makePrev(int[] a, int sup)
	{
		int n = a.length;
		int[] mnext = new int[sup];
		Arrays.fill(mnext, -1);
		int[] next = new int[n];
		for(int i = 0;i < n;i++){
			next[i] = mnext[a[i]];
			mnext[a[i]] = i;
		}
		return next;
	}

	public static int factorFast(int n, int[] lpf)
	{
		int ret = 1;
		int e = 0;
		int last = -1;
		while(lpf[n] > 0) {
			int p = lpf[n];
			if (last != p) {
				if (last > 0 && e % 2 == 1) {
					ret = ret * last;
				}

				last = p;
				e = 1;
			} else {
				e++;
			}
			n /= p;
		}

		if(last > 0 && e % 2 == 1){
			ret *= last;
		}
		return ret;
	}


	public static int[]... Which one is the correct time complexity of the code snippet: constant, linear, quadratic, cubic, log(n), nlog(n) or NP-hard?