#include <bits/stdc++.h>

using namespace std;

struct dsu {
  vector<int> par, rank, sz;
  int cnt;
  dsu(int n) {
    par.resize(n);
    iota(par.begin(), par.end(), 0);
    rank.resize(n, 0);
    sz.resize(n, 1);
    cnt = n;
  }
  int find(int x) {
    return x == par[x] ? x : par[x] = find(par[x]);
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (rank[x] < rank[y]) swap(x, y);
    par[y] = x, sz[x] += sz[y];
    if (rank[x] == rank[y]) rank[x] += 1;
    --cnt; return true;
  }
  int size(int x) {
    return sz[find(x)];
  }
  int sets() {
    return cnt;
  }
  bool isSame(int x, int y) {
    return find(x) == find(y);
  }
};

void solve(int cs) {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  dsu d(n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (__gcd(a[i], a[j]) > 1) {
        d.unite(i, j);
      }
    }
  }
  vector<vector<int>> who(n);
  for (int i = 0; i < n; i++) {
    who[d.find(i)].push_back(a[i]);
  }
  for (auto &v : who) {
    sort(v.rbegin(), v.rend());
  }
  int64_t cur = 0, ans = 0;
  vector<int> fu(n, 0);
  for (int i = 0; i < k; i++) {
    int u = d.find(i);
    cur += who[u][fu[u]];
    fu[u] += 1;
  }
  ans = cur;
  for (int i = k; i < n; i++) {
    int u = d.find(i - k);
    fu[u] -= 1;
    cur -= who[u][fu[u]];
    u = d.find(i);
    cur += who[u][fu[u]];
    fu[u] += 1;
    ans = max(ans, cur);
  }
  cout << ans << "\n";
}

int32_t main() {
  ios::sync_with_stdio(!cin.tie(0));
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    solve(i);
  }
  return 0;
}