#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

class DSU {
public:
  DSU(int n) : Par(n), rank(n, 0), siz(n, 1) {
    for (int i = 0; i < n; ++i) {
      Par[i] = i;
    }
  }

  int Leader(int x) {
    if (Par[x] != x) {
      Par[x] = Leader(Par[x]);
    }
    return Par[x];
  }

  bool unite(int x, int y) {
    int X = Leader(x);
    int Y = Leader(y);
    if (X != Y) {
      if (rank[X] > rank[Y]) {
        Par[Y] = X;
        siz[X] += siz[Y];
      } else if (rank[X] < rank[Y]) {
        Par[X] = Y;
        siz[Y] += siz[X];
      } else {
        Par[Y] = X;
        siz[X] += siz[Y];
        ++rank[X];
      }
      return true;
    }
    return false;
  }

  int size(int x) {
    int root = Leader(x);
    return siz[root];
  }

private:
  vector<int> Par;
  vector<int> rank;
  vector<int> siz;
};

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 dsu(n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (__gcd(a[i], a[j]) > 1) {
        dsu.unite(i, j);
      }
    }
  }

  unordered_map<int, vector<int>> groups;
  for (int i = 0; i < n; i++) {
    groups[dsu.Leader(i)].push_back(a[i]);
  }

  for (auto &group : groups) {
    sort(group.second.rbegin(), group.second.rend());
  }

  vector<int> max_possible(n);
  for (int i = 0; i < n; i++) {
    int leader = dsu.Leader(i);
    max_possible[i] = groups[leader].back();
    groups[leader].pop_back();
  }

  int64_t res = 0, sum = 0;
  for (int i = 0; i < k; i++) {
    sum += max_possible[i];
  }
  res = sum;

  for (int i = k; i < n; i++) {
    sum += max_possible[i] - max_possible[i - k];
    res = max(res, sum);
  }

  cout << res << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc;
  cin >> tc;
  for (int cs = 1; cs <= tc; cs++) {
    solve(cs);
  }
  return 0;
}