func_code_string: //#pragma GCC optimize( Ofast )      #include <iostream>   #include <vector>   #include <map>   #include <algorithm>   #include <random>   #include <chrono>   #include <complex>   #include <cstdio>   #include <deque>   #include <cmath>   #include <bitset>   #include <set>   #include <cassert>      using namespace std;      #define ll long long   #define ull unsigned long long   #define pb push_back   #define se second   #define fi first   #define forn(i,n) for(int i = 0; i < (n); i++)   #define read(a) for(int i = 0; i < a.size(); i++){cin >> a[i];}   #define all(a) a.begin(),a.end()   #define make_unique(a) sort(all(a)); a.resize(unique(a.begin(),a.end())-a.begin());   const int mod = 1e9 + 7;   //#define int long long      const int N = 10000000;   int lp[N+1];   vector<int> pr;      void solve(){       int t;       cin >> t;          for (int i=2; i<=N; ++i) {           if (lp[i] == 0) {               lp[i] = i;               pr.push_back (i);           }           for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)               lp[i * pr[j]] = pr[j];       }          set<vector<int>> se;          while(t--){           int n,k;           cin >> n >> k;           vector<int> a(n);           read(a);           ll ans = 1;           se.clear();           for(int i = 0; i < n; ++i){               vector<int> qw;               int nw = a[i];               while(nw != 1){                   if(!qw.empty() && qw.back() == lp[nw]){                       qw.pop_back();                       nw /= lp[nw];                       continue;                   }                   if(qw.empty() || qw.back() != lp[nw]){                       qw.push_back(lp[nw]);                   }                   nw /= lp[nw];                                  }               if(se.count(qw)){                   ans++;                   se.clear();               }               se.insert(qw);           }           cout << ans <<   n ;       }      }            signed main() {       ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);   #ifdef Debugg       freopen( ain.txt , r ,stdin);       freopen( aout.txt , w ,stdout);   #endif       solve();   #ifdef Debugg       cout <<   n  << (double)clock()/CLOCKS_PER_SEC;   #endif   }