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;
//--------------------------------------Useful Macros------------------------------------

//-------Constants----------
#define MOD 1000000007
#define INF 1000000000000000001

//------Standard Input Output Tweaks------
#define fin freopen("D:/Programs/Competitive/input", "r", stdin);
#define fout freopen("D:/Programs/Competitive/output", "w", stdout);
#define sync ios_base::sync_with_stdio(false);
#define fastio sync cin.tie(NULL);
#define fileio fin fout

//--------Miscellaneous--------
#define F first
#define S second
#define pb push_back
#define sz(x) x.size()
#define isOdd(n) (n % 2)
#define isEven(n) (n % 2 == 0)
#define all(p) p.begin(), p.end()
#define notend(itr, s) (itr != s.end())
#define min3(a, b, c) min((a), min((b), (c)))
#define max3(a, b, c) max((a), max((b), (c)))
#define isPresent(x, s) (s.find(x) != s.end())
#define inrange(x, l, h) ((x >= l) && (x <= h))
#define myfor(x, s, e) for (int x = s; x < e; x++)
#define deb(x) cout << #x << " : " << x << endl;
#define endl '\n'

//-------------------------------------End of Macros------------------------------------

typedef long long int lli;

typedef pair<lli, lli> pii;
typedef vector<lli> vi;
typedef set<lli> si;
typedef unordered_map<lli, lli> umii;
typedef unordered_set<lli> usi;

bool CustomCompare(const pii &, const pii &);

lli modmul(lli, lli);
lli modadd(lli, lli);
lli modsub(lli, lli);
lli ncr(lli, lli);
void facto();
lli fpow(lli x, lli y, lli p = MOD);
//------------------------------Declaring Trace Functions----------------------------------

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P);
template <class T>
ostream &operator<<(ostream &os, vector<T> V);
template <class T>
ostream &operator<<(ostream &os, set<T> S);
template <class T>
ostream &operator<<(ostream &os, unordered_set<T> S);
template <class T, class T1>
ostream &operator<<(ostream &os, map<T, T1> S);
template <class T, class T1>
ostream &operator<<(ostream &os, unordered_map<T, T1> S);

//-----------------------------------End of Declarations------------------------------------
vi fact(307, 0);
//---------------------------------------SOLVE HERE----------------------------------------
int N = 10000001;
vector<int> mypv;
void primesg()
{
    int n = N;
    vector<int> primes(n, 1);
    for (int i = 0; i < n; i++)
        primes[i] = i;
    vector<int> allp;
    primes[0] = primes[1] = 0;
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (primes[i] == i)
        {
            // allp.pb(i);
            for (int j = i * i; j < n; j += i)
            {
                primes[j] = i;
            }
        }
    }
    for (int i = 2; i < n; i++)
    {
        if (primes[i] == i)
            allp.pb(i);
    }
    mypv = vector<int>(N, 1);
    for (int i = 2; i < n; i++)
    {
        int p = primes[i];
        mypv[i] = mypv[i / p];
        if (mypv[i] % p == 0)
            mypv[i] /= p;
        else
            mypv[i] *= p;
    }
    // cout << mypv << endl;
}
void solve()
{
    int n, k;
    cin >> n >> k;
    vi ar(n);
    for (int i = 0; i < n; i++)
        cin >> ar[i];
    set<lli> s;
    int ans = 1;
    for (int i = 0; i < n; i++)
    {
        if (isPresent(mypv[ar[i]], s))
        {
            s.clear();
            s.insert(mypv[ar[i]]);
            ans++;
        }
        else
        {
            s.insert(mypv[ar[i]]);
        }
    }
    cout << ans << endl;
}
//----------------------------------------MAIN HERE----------------------------------------

int main()
{
    // facto();
#ifndef ONLINE_JUDGE
    fileio;
    // fin;
#endif
    fastio;
    int t = 1;
    primesg();
    cin >> t;
    int i = 1;
    while (i <= t)
    {
        // cout << "Case #" << i << ": ";
        solve();
        i++;
    }

    // cout << 3 << endl
    //      << 2 << endl
    //      << 1 << endl;
    return 0;
}
//----------------------------------Defining Trace Functions------------------------------

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P)
{
    return os << "(" << P.first << ", " << P.second << ")";
}

template <class T>
ostream &operator<<(ostream &os, vector<T> V)
{
    if (sz(V))
    {
        os << "[" << V[0];
        for (int i = 1; i < sz(V); i++)
            os << ", " << V[i];
        return os << "]";
    }
    return os << "[]";
}

template <class T>
ostream &operator<<(ostream &os, set<T> S)
{
    os << "{";
    for (auto s : S)
        os << s << ", ";
    return os << "}";
}

template <class T>
ostream &operator<<(ostream &os, unordered_set<T> S)
{
    os << "{";
    for (auto s : S)
        os << s << ", ";
    return os << "}";
}

template <class T, class T1>
ostream &operator<<(ostream &os, map<T, T1> S)
{
    os << "{" << endl;
    for (auto s : S)
        os << "\t" << s.first << " : " << s.second << "," << endl;
    return os << "}" << endl;
}

template <class T, class T1>
ostream &operator<<(ostream &os, unordered_map<T, T1> S)
{
    os << "{" << endl;
    for (auto s : S)
        os << "\t" << s.first << " : " << s.second << "," << endl;
    return os << "}" << endl;
}

//---------------------------------------End of Definitions--------------------------------

//stable sort by first then second both in increasing
bool CustomCompare(const pii &i, const pii &j)
{
    if (i.first == j.first)
        return i.second < j.second;
    return i.first < j.first;
}

//------------------------------------Modular Arithmetic-----------------------------------
lli modmul(lli a, lli b)
{
    lli ret = (a % MOD) * (b % MOD);
    ret %= MOD;
    return ret;
}
lli modadd(lli a, lli b)
{
    lli ret = (a % MOD) + (b % MOD);
    ret %= MOD;
    return ret;
}
lli modsub(lli a, lli b)
{
    a = a % MOD;
    b = b % MOD;
    if (a < b)
        a += MOD;
    lli ret = a - b;
    ret %= MOD;
    return ret;
}
lli fpow(lli x, lli y, lli p)
{
    // lli p = MOD;
    x = x % p;
    lli sum = 1;
    while (y)
    {
        if (y & 1)
            sum = sum * x;
        sum %= p;
        y = y >> 1;
        x = x * x;
        x %= p;
    }
    return sum;
}
void facto()
{
    fact[0] = 1;
    fact[1] = 1;
    for (int i = 2; i < 3000007; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
}
lli ncr(lli n, lli r)
{
    if (r > n)
        return 0;
    lli res = 1;
    res = fact[n];
    res = (res * (fpow(fact[r], MOD - 2))) % MOD;
    res = (res * (fpow(fact[n - r], MOD - 2))) % MOD;
    return res;
}