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.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class E1708 {

    static BufferedReader br;
    static long mod = 1000000000 + 7;
    static TreeSet<Integer> p = new TreeSet<>();

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        int tc = 1;
        tc = cinI();
      //  sieve();
        //.out.println(p.size());
        StringBuilder ob =new StringBuilder();
        int[] product = new int[100_00_00_0+1];
        while (tc-- > 0) {

          int[] nk =readArray(2,0,0);
          int n = nk[0];
          int[] ar=readArray(n,0,0);
          int ans=1;
          HashSet<Integer> numberReq=new HashSet<>();
          boolean isSq = false;
          for(int i=0;i<n;i++){
              int r=1;


                  if(product[ar[i]]==0) {
                      product[ar[i]]=find(ar[i]);
                  }

                      r=product[ar[i]];

                  if(numberReq.contains(r)){
                      ans+=1;
                      numberReq=new HashSet<>();
                      numberReq.add(r);
                  }
                  else{
                      numberReq.add(r);
                  }
                //  product[ar[i]]=r;
               //   System.out.println(r+" "+ans+" "+numberReq+" i  "+i);

          }
           ob.append(ans+"\n");
        }
        System.out.println(ob.toString().trim());
    }

    private static int find(int i) {

        for(int j=2;j*j<=i;j+=1){

            int r = j*j;

            while (i%r==0)i=i/r;
        }
        return i;
    }

    private static boolean check(int elem) {
        if(elem==1){
            return true;
        }
        int l = (int)Math.sqrt(elem);
        if(l*l==elem)return true;
        return false;
    }


    private static int dfs(TreeMap<Integer, HashSet<Integer>> graph, boolean[] vis, Integer key, Stack<Integer> st) {
        if (st.size() == 0) {
            return 0;
        }
        int par = st.pop();

        HashSet<Integer> child = graph.get(par);
        vis[par] = true;
        int nodes = 1;
        for (int c : child) {
            if (vis[c] == false) {
                st.add(c);
                nodes += dfs(graph, vis, c, st);
            }
        }
        return nodes;
    }


    public static boolean isSorted(int[] arr) {

        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                return false;
            }
        }
        return true;
    }


    private static long gcd(long a, long b) {
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a % b, b);
        return gcd(a, b % a);
    }


    public static long min(long a, long b) {
        return Math.min(a, b);
    }

    public static int min(int a, int b) {
        return Math.min(a, b);
    }


    public static void sieve() {
        int[] pf = new int[10000000 + 1];
        //0 prime //1 not prime
        pf[0] = 1;
        pf[1] = 1;
        p.add(2);
        for (int j = 3; j <= 10000000; j+=2) {

            if (pf[j] == 0) {
                p.add(j);
                for (long k = (long)j * j; k < pf.length; k += j) {
                    pf[(int)k] = 1;
                }
            }
        }

    }


    public static int[] readArray(int n, int x, int z) throws Exception {
        int[] arr = new int[n];
        String[] ar = cinA();
        for (int i = x; i < n + x; i++) {
            arr[i] = getI(ar[i - x]);
        }
        return arr;
    }

    public static long[] readArray(int n, int x) throws Exception {
        long[] arr = new long[n];
        String[] ar = cinA();
        for (int i = x; i < n + x; i++) {
            arr[i] = getL(ar[i - x]);
        }
        return arr;
    }

    public static void arrinit(String[] a, long[] b) throws Exception {
        for (int i = 0; i < a.length; i++) {
            b[i] = Long.parseLong(a[i]);
        }
    }

    public static HashSet<Integer>[] Graph(int n, int edge, int directed) throws Exception {
        HashSet<Integer>[] tree = new HashSet[n];

        for (int j = 0; j < edge; j++) {

            String[] uv = cinA();
            int u = getI(uv[0]);
            int v = getI(uv[1]);
            if (directed == 0) {

                tree[v].add(u);
            }
            tree[u].add(v);
        }
        return tree;
    }

    public static void arrinit(String[] a, int[] b) throws Exception {
        for (int i = 0; i < a.length; i++) {
            b[i] = Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }

    public static String[] cinA(int x) throws Exception {
        return br.readLine().split("");
    }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static long max(long a, long b) {
        return Math.max(a, b);
    }

    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}