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] 
/*
++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>+++.<++.>>+++++++++++++++++++.----------------------.+++++++++++++.++++++.<<.>>--.---..--.<<.+++++++++++++.-------------.>.<.>>++++++++++.----------------------.+++++++++++++.++++++.<<.>>-.---.---------------.++.++.<<++++++++++++.------------.>>++++++++++++++++++.--------------.+++..<<.>>+++++++++++++.----------.++++++.<<.>>---------------.+++++++++++++++.------------------.++++++++.--.+++++.-------.<<.>>+++++.-------.----.+++++++++++++++++++++.-----------------.<<.>>+++++++++++++++.------------.+.++++++++++.<<.>>---.----.-----------.++.++.<<+.
*/
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define debug(statement) \
    cerr << statement << endl
#define debug_variable(var) \
    cerr << (#var) << ": " << var << endl

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    for (auto element : v)
    {
        os << element << " ";
    }
    return os;
}

template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> &p)
{
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}

template <typename T>
ostream &operator<<(ostream &os, set<T> &v)
{
    auto endit = v.end();
    endit--;
    os << "[";
    for (auto it = v.begin(); it != v.end(); it++)
    {
        os << *it;
        if (it != endit)
        {
            os << ", ";
        }
    }
    os << "]";
    return os;
}

template <typename T, typename S>
ostream &operator<<(ostream &os, map<T, S> &v)
{
    auto endit = v.end();
    endit--;
    os << "{";
    for (auto it = v.begin(); it != v.end(); it++)
    {
        os << "(" << (*it).first << " : " << (*it).second << ")";
        if (it != endit)
        {
            os << ", ";
        }
    }
    os << "}";
    return os;
}

void io_on()
{
#ifndef ONLINE_JUDGE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
#endif
}

void fastscan(long long &number)
{
    //variable to indicate sign of input number
    bool negative = false;
    int c;

    number = 0;

    // extract current character from buffer
    c = getchar();
    if (c == '-')
    {
        // number is negative
        negative = true;

        // extract the next character from the buffer
        c = getchar();
    }

    // Keep on extracting characters if they are integers
    // i.e ASCII Value lies from '0'(48) to '9' (57)
    for (; (c > 47 && c < 58); c = getchar())
        number = number * 10 + c - 48;

    // if scanned input has a negative sign, negate the
    // value of the input number
    if (negative)
        number *= -1;
}

vector<bool> sieve(1e6 + 1, true);
vector<long long> sieveCount(1e6 + 1, 0);
vector<long long> finalSieve;
void sieveCompute()
{
    sieve[0] = false;
    sieve[1] = false;
    long long n = 1e4+10;
    long long sn = sqrt(n);
    for (long long i = 2; i <= sn; i++)
    {
        if (sieve[i])
        {
            for (long long j = i * i; j <= n; j += i)
            {
                sieve[j] = false;
            }
        }
    }

    long long ctr = 0;
    for (long long i = 0; i < n; i++)
    {
        if (sieve[i])
        {
            ctr++;
        }
        sieveCount[i] = ctr;
    }

    for(long long i = 1; i <= n; i++)
    {
        if(sieve[i]){
            finalSieve.push_back(i);
        }
    }
}


void solve()
{
    long long n, k;
    cin >> n >> k;
    vector<long long> v(n);
    for (long long i = 0; i < n; i++)
    {
        cin >> v[i];
    }

    vector<long long> aux;
    for (long long i = 0; i < n; i++)
    {
        long long x = 1;
        long long temp = v[i];
        long long ctr = 0;
        while (temp > 1)
        {
            if(finalSieve[ctr] > sqrt(v[i])){
                break;
            }
            long long ctr_secondary = 0;
            while(ctr < finalSieve.size() && temp%finalSieve[ctr] == 0){
                temp = temp / finalSieve[ctr];
                ctr_secondary++;
            }
            if(ctr_secondary % 2 == 1){
                x *= finalSieve[ctr];
            }
            ctr++;
        }
        if(temp != 1){
        x = x * temp;
        }
        aux.push_back(x);
    }
    // for(long long i = 0; i < n; i++)
    // {
    //     cout << aux[i] << " ";
    // }
    // cout << nl;
    unordered_set<long long> s;
    long long result = 1;
    for (long long i = 0; i < n; i++)
    {
        if (s.count(aux[i]) == 0)
        {
            s.insert(aux[i]);
        }
        else
        {
            s.clear();
            s.insert(aux[i]);
            result++;
        }
    }
    cout << result << nl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    io_on();
    sieveCompute();
    // for(long long i = 0; i < 100; i++)
    // {
    //     cout << finalSieve[i] << " ";
    // }
    // cout << nl;
    int test;
    cin >> test;
    while (test-- > 0)
    {
        solve();
    }
    return 0;
}