#include <bits/stdc++.h>
using namespace std;
vector<long long> p;
long long ans = 0;
void prime() {
  map<long long, long long> M;
  for (int i = 2; i * i <= 1e7; i++) {
    if (M[i]) continue;
    for (int j = 2 * i; j <= 1e4; j += i) {
      M[j]++;
    }
    if (!M[i]) p.push_back(i);
  }
}
int factor(int a) {
  for (auto x : p) {
    int b = x * x;
    if (b > a) break;
    while (a % b == 0) {
      a /= b;
    }
  }
  return a;
}
int main() {
  int T;
  cin >> T;
  prime();
  while (T--) {
    long long n, k, i;
    ans = 1;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x : a) cin >> x;
    map<long long, long long> m;
    for (i = 0; i < n; i++) {
      int nm = factor(a[i]);
      if (m[nm] && i > 0) {
        ans++;
        m.clear();
        m[factor(a[i])]++;
      } else
        m[nm]++;
    }
    cout << ans << endl;
  }
  return 0;
}
