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.util.*;

public final class Solution {


    static PrintWriter out = new PrintWriter(System.out);
    static FastReader in = new FastReader();
    static long mod = (long) 1e9 + 7;
    static Pair[] moves = new Pair[]{new Pair(-1, 0), new Pair(1, 0), new Pair(0, -1), new Pair(0, 1)};

    public static void main(String[] args) {
        int t = i();
        sieveLinear(10000001);

        while (t-- > 0) {
            int n = i();
            int k = i();
            HashSet<Integer> hs = new HashSet<>();
            int ans = 1;
            for (int i = 0; i < n; i++) {
                int x = i();
                int cur = 1;
                while (x > 1) {
                    int prime = lp[x];
                    boolean powodd = false;
                    while (x % prime == 0) {
                        powodd = !powodd;
                        x /= prime;
                    }
                    if (powodd) {
                        cur *= prime;
                    }
                }
                if (hs.contains(cur)) {
                    ans++;
                    hs = new HashSet<>();
                }
                hs.add(cur);
            }
            out.println(ans);
        }
        out.flush();
    }

    static int sd(long i) {
        int d = 0;
        while (i > 0) {
            d += i % 10;
            i = i / 10;
        }
        return d;
    }

    static int[] lp;

    static void sieveLinear(int N) {
        int[] primes = new int[N];
        int idx = 0;
        lp = new int[N + 1];
        for (int i = 2; i <= N; i++) {
            if (lp[i] == 0) {
                primes[idx++] = i;
                lp[i] = i;
            }
            int curLP = lp[i];
            for (int j = 0; j < idx; j++) {
                int p = primes[j];
                if (p > curLP || (long) p * i > N) {
                    break;
                } else {
                    lp[p * i] = p;
                }
            }
        }
    }


    static int lower(long A[], long x) {
        int l = -1, r = A.length;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (A[m] >= x) {
                r = m;
            } else {
                l = m;
            }
        }
        return r;
    }

    static int upper(long A[], long x) {
        int l = -1, r = A.length;
        while (r - l > 1) {
            int m = (l + r) / 2;
            if (A[m] <= x) {
                l = m;
            } else {
                r = m;
            }
        }
        return l;
    }

    static void swap(int A[], int a, int b) {
        int t = A[a];
        A[a] = A[b];
        A[b] = t;
    }

    static int lowerBound(int A[], int low, int high, int x) {
        if (low > high) {
            if (x >= A[high]) {
                return A[high];
            }
        }

        int mid = (low + high) / 2;

        if (A[mid] == x) {
            return A[mid];
        }

        if (mid > 0 && A[mid - 1] <= x && x < A[mid]) {
            return A[mid - 1];
        }

        if (x < A[mid]) {
            return lowerBound(A, low, mid - 1, x);
        }

        return lowerBound(A, mid + 1, high, x);
    }


    static long pow(long a, long b) {
        long pow = 1;
        long x = a;
        while (b != 0) {
            if ((b & 1) != 0) {
                pow = (pow * x) % mod;
            }
            x = (x * x) % mod;
            b /= 2;
        }
        return pow;
    }

    static boolean isPrime(long N) {
        if (N <= 1) {
            return false;
        }
        if (N <= 3) {
            return true;
        }
        if (N % 2 == 0 || N % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= N; i = i + 6) {
            if (N % i == 0 || N % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }

    static void print(char A[]) {
        for (char c : A) {
            out.print(c);
        }
        out.println();
    }

    static void print(boolean A[]) {
        for (boolean c : A) {
            out.print(c + " ");
        }
        out.println();
    }

    static void print(int A[]) {
        for (int c : A) {
            out.print(c + " ");
        }
        out.println();
    }

    static void print(long A[]) {
        for (long i : A) {
            out.print(i + " ");
        }
        out.println();

    }

    static void print(List<Integer> A) {
        for (int a : A) {
            out.print(a + " ");
        }
    }

    static void printYes() {
        out.println("YES");
    }

    static void printNo() {
        out.println("NO");
    }

    static int i() {
        return in.nextInt();
    }

    static long l() {
        return in.nextLong();
    }

    static String s() {
        return in.nextLine();
    }

    static int[] input(int N) {
        int A[] = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = in.nextInt();
        }
        return A;
    }

    static long[] inputLong(int N) {
        long A[] = new long[N];
        for (int i = 0; i < A.length; i++) {
            A[i] = in.nextLong();
        }
        return A;
    }

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

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

}

class SegmentTree {

    long[] t;

    public SegmentTree(int n) {
        t = new long[n + n];
        Arrays.fill(t, Long.MIN_VALUE);
    }

    public long get(int i) {
        return t[i + t.length / 2];
    }

    public void add(int i, long value) {
        i += t.length / 2;
        t[i] = value;
        for (; i > 1; i >>= 1) {
            t[i >> 1] = Math.max(t[i], t[i ^ 1]);
        }
    }

    // max[a, b]
    public long max(int a, int b) {
        long res = Long.MIN_VALUE;
        for (a += t.length / 2, b += t.length / 2; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
            if ((a & 1) != 0) {
                res = Math.max(res, t[a]);
            }
            if ((b & 1) == 0) {
                res = Math.max(res, t[b]);
            }
        }
        return res;
    }
}

class Pair {

    int i, j;

    Pair(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

class FastReader {

    BufferedReader br;
    StringTokenizer st;

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

    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;
    }


}
