#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define ll long long
#define vll vector<ll>
#define vvll vector<vll>
#define FOR(i,a,b) for(ll i = a;i<b;i++)
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pb push_back
#define Ye cout<<"YES\n"
#define No cout<<"NO\n";
void in(int n, int a[]){
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
}
void out(int n, int a[]){
    for(int i = 0;i<n;i++){
        cout << a[i] << " ";
    }
}
const int maxn = 2e5+5;
const int maxp = 1e7+5;
int spf[maxp];
void sieve(){
    for(int i = 0;i<maxp;i++){
        spf[i] = i;
    }
    for(int i = 2;i*i<maxp;i++){
        if(spf[i] == i){
            for(int j = i*i;j<maxp;j+=i){
                if(spf[j] == j){
                    spf[j] = i;
                }
            }
        }
    }
}
namespace u{
    int n,k;
    int a[maxn];
    int mask[maxn];
    void solve(){
        cin >> n >> k;
        in(n,a);
        for(int i = 0;i<n;i++){
            mask[i] = 0;
        }
        vector<vector<pair<int,int>>> f(n+5,vector<pair<int,int>>());
        //phan tich thua so nguyen to
        for(int i = 0;i<n;i++){
            int x = a[i];
            if(x<2){
                f[i].push_back({1,1});
            }
            while(x>1){
                int p = spf[x];
                int cnt = 0;
                while(x%p==0){
                    cnt++;
                    x/=p;
                }
                f[i].push_back({p,cnt});
            }
        }
        //tinh mask
        for(int i = 0;i<n;i++){
            int h = 1;
            for(int j = 0;j<(int)f[i].size();j++){
                int p = f[i][j].first;
                int q = f[i][j].second%2;
                if(q == 1){
                    h*=p;
                }
            }
            mask[i] = h;
        }
        int l = 0; int r = 0;
        int ans = 0;
        while(l<=r && r < n){
            map<int,int> cnt;
            while(cnt.find(mask[r]) == cnt.end() && r < n){
                cnt[mask[r]]++;
                r++;
            }
            l = r;
            ans++;
        }
        cout << ans << "\n";
    }
}
signed main(){
    fast;
    sieve();
    int t = 1; cin >> t;
    while(t--) u::solve();
}