#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
using namespace std;

const int mxN = 1e4 + 2;
vector<vector<int>> g(mxN);
vector<vector<int>> who(mxN);
vector<int> Par(mxN), siz(mxN), rnk(mxN);

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 (rnk[X] > rnk[Y]) {
      Par[Y] = X;
      siz[X] += siz[Y];
    } else if (rnk[X] < rnk[Y]) {
      Par[X] = Y;
      siz[Y] += siz[X];
    } else {
      Par[Y] = X;
      siz[X] += siz[Y];
      ++rnk[X];
    }
    return true;
  }
  return false;
}

void solve(int cs) {
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    Par[i] = i, rnk[i] = 0, siz[i] = 1;
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (__gcd(a[i], a[j]) > 1) {
        unite(i, j);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    g[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;
}