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.util.Map.Entry;

import java.math.*;
import java.io.*;

public class Main {
	static final int MAXN = 10000010;

	public static void main(String[] args) throws FileNotFoundException {
		InputReader in = new InputReader(System.in);
		// Scanner in = new Scanner(System.in);
		// Scanner in = new Scanner(new BufferedReader(new
		// InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(System.out);
		// InputReader in = new InputReader(new
		// File("ethan_traverses_a_tree.txt"));
		// PrintWriter out = new PrintWriter(new
		// File("ethan_traverses_a_tree-output.txt"));

		int[] sp = getsingleproduct();

		int pi = in.nextInt();
		for (int qi = 0; qi < pi; qi++) {
			int n = in.nextInt();
			int k = in.nextInt();

			int[] a = new int[n];
			for (int i = 0; i < n; i++) {
				int temp = in.nextInt();
				a[i] = sp[temp];
			}

			int[][] maxright = new int[k + 1][n];
			for (int i = 0; i < k + 1; i++) {
				Map<Integer, Integer> map = new HashMap<Integer, Integer>();

				int nowcount = 0;
				int end = -1;
				for (int start = 0; start < n; start++) {
					while (true) {
						if (end + 1 >= n) {
							maxright[i][start] = end;
							break;
						}

						if (map.containsKey(a[end + 1]) == false) {
							mapadd(map, a[end + 1]);
							end++;
						} else if (nowcount < i) {
							nowcount++;
							mapadd(map, a[end + 1]);
							end++;
						} else {
							maxright[i][start] = end;
							break;
						}
					}

					if (map.get(a[start]) == 2) {
						nowcount--;
					}
					mapdelete(map, a[start]);
				}
			}

			int[][] dp = new int[k + 1][n + 1];
			for (int i = 0; i < k + 1; i++) {
				for (int j = n; j >= 0; j--) {
					if (j == n) {
						dp[i][j] = 0;
					} else {
						int min = n + 10;
						for (int nowk = 0; nowk <= i; nowk++) {
							min = Math.min(min, dp[i - nowk][maxright[nowk][j] + 1] + 1);
						}
						dp[i][j] = min;
					}
				}
			}

			out.printf("%d\n", dp[k][0]);
		}

		out.close();
	}

	public static void mapadd(Map<Integer, Integer> map, int key) {
		if (map.containsKey(key) == false) {
			map.put(key, 0);
		}

		map.put(key, map.get(key) + 1);
	}

	public static void mapdelete(Map<Integer, Integer> map, int key) {
		if (map.get(key) == 1) {
			map.remove(key);
		} else {
			map.put(key, map.get(key) - 1);
		}
	}

	public static int[] getsingleproduct() {
		int[] lastprime = new int[MAXN];

		for (int i = 2; i * i < MAXN; i++) {
			if (lastprime[i] == 0) {
				for (int j = i; j * i < MAXN; j++) {
					if (lastprime[j * i] == 0) {
						lastprime[j * i] = i;
					}
				}
			}
		}

		int[] singleproduct = new int[MAXN];
		singleproduct[1] = 1;
		for (int i = 2; i < MAXN; i++) {
			if (lastprime[i] == 0) {
				singleproduct[i] = i;
			} else {
				int k = lastprime[i];

				int count = 0;
				int tmpi = i;
				while (tmpi % k == 0) {
					tmpi = tmpi / k;
					count++;
				}

				if (count % 2 == 0) {
					singleproduct[i] = singleproduct[tmpi];
				} else {
					singleproduct[i] = singleproduct[tmpi] * k;
				}
			}
		}

		return singleproduct;
	}

	static class InputReader {
		BufferedReader br;
		StringTokenizer st;

		public InputReader(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public InputReader(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

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

		public boolean hasNext() {
			while (st == null || !st.hasMoreTokens()) {
				String s = null;
				try {
					s = br.readLine();
				} catch (IOException e) {
					e.printStackTrace();
				}
				if (s == null)
					return false;
				st = new StringTokenizer(s);
			}
			return true;
		}

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

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

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