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 javax.swing.RowFilter.Entry;
import javax.swing.text.AbstractDocument.BranchElement;
import javax.swing.text.html.parser.Entity;

import java.io.*;

public class Absent_Students {
	static PrintWriter pw;
	static BufferedReader br;
	static int inf = (int) 1e9;
	static long mod = (long) 1e9 + 7;
	static int[][] memo;
	static boolean[][] ok;
	static int[] a;
	static ArrayList<Integer> primes;
	static int[] isComposite;

	static HashMap<Integer, Integer> hm;

	static int[] type;

	public static void main(String[] args) throws NumberFormatException, IOException, InterruptedException {
		Scanner sc = new Scanner(System.in);
//		br = new BufferedReader(new InputStreamReader(System.in));
		pw = new PrintWriter(System.out);
		sieve(10000001);
		int t = sc.nextInt();
		while (t-- > 0) {
			int n = sc.nextInt();
			int k = sc.nextInt();
			int[] a = new int[n];
			HashSet<Integer> hs = new HashSet<>();
			int c = 1;
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
				int num = getNum(a[i]);
				if (hs.contains(num)) {
					c++;
					hs = new HashSet<>();
				}
				hs.add(num);
			}
			pw.println(c);
		}
		pw.flush();
	}

	static int getNum(int N) // O(sqrt(N) / ln sqrt(N))
	{
		ArrayList<Integer> factors = new ArrayList<Integer>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);
		int num = 1;
		while (p * p <= N) {
			int c = 0;
			while (N % p == 0) {
				c++;
				N /= p;
			}
			if (c % 2 == 1)
				num *= p;
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			num *= N; // for integers whose largest prime factor has a power of 1
		return num;
	}

	static final int INF = (int) 1e9; // don't increase, avoid overflow
	static ArrayList<Edge>[] adjList;
	static int V;

	/*
	 * 1. Dijkstra's Algorithm for SSSP on weighted graphs
	 */
	static int dijkstra(int S, int T) // O(E log E)
	{
		int[][] dist = new int[4][V];
		for (int i = 0; i < dist.length; i++) {
			Arrays.fill(dist[i], INF);
		}
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
		for (int i = 0; i < V; i++) {
			if (type[i] == 1) {
				pq.add(new Edge(i, 0, 1));
				dist[1][i] = 0;
			} else if (type[i] == 2) {
				pq.add(new Edge(i, 0, 2));
				dist[2][i] = 0;
			}
		}
		while (!pq.isEmpty()) {
			Edge cur = pq.remove();
			if (cur.node == T && cur.state == 3)
				return cur.cost;
			if (cur.cost > dist[cur.state][cur.node]) // lazy deletion
				continue;
			for (Edge nxt : adjList[cur.node]) {
				if (hm.get(nxt.node) == 0) {
					if (cur.cost + nxt.cost < dist[cur.state][nxt.node])
						pq.add(new Edge(nxt.node, dist[cur.state][nxt.node] = cur.cost + nxt.cost, cur.state));
				} else if (hm.get(nxt.node) == 1) {
					if (cur.state == 0 || cur.state == 1) {
//						System.out.println(nxt.cost+"pplk");
						if (cur.cost + nxt.cost < dist[1][nxt.node])
							pq.add(new Edge(nxt.node, dist[1][nxt.node] = cur.cost + nxt.cost, 1));
					} else {
						if (cur.cost + nxt.cost < dist[3][nxt.node])
							pq.add(new Edge(nxt.node, dist[3][nxt.node] = cur.cost + nxt.cost, 3));
					}
				} else {
					if (cur.state == 0 || cur.state == 2) {
						if (cur.cost + nxt.cost < dist[2][nxt.node])
							pq.add(new Edge(nxt.node, dist[2][nxt.node] = cur.cost + nxt.cost, 2));
					} else {
						if (cur.cost + nxt.cost < dist[3][nxt.node])
							pq.add(new Edge(nxt.node, dist[3][nxt.node] = cur.cost + nxt.cost, 3));
					}
				}
			}
		}
		return -1;
	}

	static class Edge implements Comparable<Edge> {
		int node, cost, state;

		Edge(int a, int b) {
			node = a;
			cost = b;
		}

		Edge(int a, int b, int s) {
			node = a;
			cost = b;
			state = s;
		}

		public int compareTo(Edge e) {
			return cost - e.cost;
		}
	}

	static class SegmentTree { // 1-based DS, OOP

		int N; // the number of elements in the array as a power of 2 (i.e. after padding)
		long[] array, sTree, lazy;

		SegmentTree(long[] in) {
			array = in;
			N = in.length - 1;
			sTree = new long[N << 1]; // no. of nodes = 2*N - 1, we add one to cross out index zero
			lazy = new long[N << 1];
			build(1, 1, N);
		}

		void build(int node, int b, int e) // O(n)
		{
			if (b == e)
				sTree[node] = array[b];
			else {
				int mid = b + e >> 1;
				build(node << 1, b, mid);
				build(node << 1 | 1, mid + 1, e);
				sTree[node] = Math.max(sTree[node << 1], sTree[node << 1 | 1]);
			}
		}

		void update_point(int index, int val) // O(log n)
		{
			index += N - 1;
			sTree[index] = val;
			while (index > 1) {
				index >>= 1;
				sTree[index] = Math.max(sTree[index << 1], sTree[index << 1 | 1]);
			}
		}

		void update_range(int i, int j, int val) // O(log n)
		{
			update_range(1, 1, N, i, j, val);
		}

		void update_range(int node, int b, int e, int i, int j, int val) {
			if (i > e || j < b)
				return;
			if (b >= i && e <= j) {
				sTree[node] += (e - b + 1) * val;
				lazy[node] += val;
			} else {
				int mid = b + e >> 1;
				propagate(node, b, mid, e);
				update_range(node << 1, b, mid, i, j, val);
				update_range(node << 1 | 1, mid + 1, e, i, j, val);
				sTree[node] = sTree[node << 1] + sTree[node << 1 | 1];
			}

		}

		void propagate(int node, int b, int mid, int e) {
			lazy[node << 1] += lazy[node];
			lazy[node << 1 | 1] += lazy[node];
			sTree[node << 1] += (mid - b + 1) * lazy[node];
			sTree[node << 1 | 1] += (e - mid) * lazy[node];
			lazy[node] = 0;
		}

		long query(int i, int j) {
			return query(1, 1, N, i, j);
		}

		long query(int node, int b, int e, int i, int j) // O(log n)
		{
			if (i > e || j < b)
				return 0;
			if (b >= i && e <= j)
				return sTree[node];
			int mid = b + e >> 1;
			propagate(node, b, mid, e);
			long q1 = query(node << 1, b, mid, i, j);
			long q2 = query(node << 1 | 1, mid + 1, e, i, j);
			return Math.max(q1, q2);

		}

	}

	static void sieve(int N) // O(N log log N)
	{
		isComposite = new int[N + 1];
		isComposite[0] = isComposite[1] = 1; // 0 indicates a prime number
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i) // can loop till i*i <= N if primes array is not needed O(N log log sqrt(N))
			if (isComposite[i] == 0) // can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				if (1l * i * i <= N)
					for (int j = i * i; j <= N; j += i) // j = i * 2 will not affect performance too much, may alter in
														// modified sieve
						isComposite[j] = 1;
			}
	}

	static ArrayList<Integer> primeFactors(int N) // O(sqrt(N) / ln sqrt(N))
	{
		ArrayList<Integer> factors = new ArrayList<Integer>(); // take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while (p * p <= N) {
			while (N % p == 0) {
				factors.add(p);
				N /= p;
			}
			p = primes.get(++idx);
		}

		if (N != 1) // last prime factor may be > sqrt(N)
			factors.add(N); // for integers whose largest prime factor has a power of 1
		return factors;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

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

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean nxtEmpty() throws IOException {
			String line = br.readLine();
			if (line.isEmpty())
				return true;
			st = new StringTokenizer(line);
			return false;
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	static class pair implements Comparable<pair> {
		int x;
		int y;
		int idx;
		int dir;

		public pair(int d, int u) {
			x = d;
			y = u;
		}

		public pair(int d, int u, int i, int di) {
			x = d;
			y = u;
			idx = i;
			dir = di;
		}

		public int compareTo(pair o) {
			if (x == o.x)
				return y - o.y;
			return x - o.x;
		}

	}

	static class pair2 implements Comparable<pair2> {
		int x;
		int y;

		public pair2(int d, int u) {
			x = d;
			y = u;
		}

		public int compareTo(pair2 o) {
			return y - o.y;
		}

	}

	static int[] nxtarr() throws IOException {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] a = new int[st.countTokens()];
		for (int i = 0; i < a.length; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		return a;
	}

	static long pow(long a, long e) // O(log e)
	{
		long res = 1;
		while (e > 0) {
			if ((e & 1) == 1)
				res *= a;
			a *= a;
			e >>= 1;
		}
		return res;
	}

	static int gcd(int a, int b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}
}
