#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;
};

const int mxN = 1e4;
vector<vector<int>> g(mxN);
vector<vector<int>> who(mxN);

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 + 1);
  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);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    g[dsu.Leader(i)].push_back(i);
  }

  for (int i = 0; i < n; i++) {
    for (auto id : g[i]) {
      who[i].push_back(a[id]);
    }
    sort(who[i].rbegin(), who[i].rend());
  }

  int64_t res = 0;
  for (int i = 0; i <= n - k; i++) {
    int64_t sum = 0;
    for (int j = 0; j < n; j++) {
      int f = 0;
      for (auto id : g[j]) {
        if (id >= i && id < i + k) {
          sum += who[j][f++];
        }
      }
    }
    res = max(res, sum);
  }
  cout << res << "\n";
  for (int i = 0; i < n; i++) {
    g[i].clear(), who[i].clear();
  }
}

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