#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 + 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);
      }
    }
  }
  unordered_map<int, vector<int>> g;
  for (int i = 0; i < n; i++) {
    int L = dsu.Leader(i);
    g[L].push_back(i);
  }
  unordered_map<int, vector<pair<int,int>>> who;
  for (int i = 0; i < n; i++) {
    int L = dsu.Leader(i);
    for (auto &id : g[L]) {
      if (__gcd(a[i], a[id]) > 1) {
        who[i].push_back({a[id], id});
      }
    }
    who[i].push_back({a[i], i});
    sort(who[i].rbegin(), who[i].rend());
  }
  int64_t res = 0, sum = 0;
  unordered_map<int,int> taken;
  for (int i = 0; i < n; i++) {
    for (int j = i; j < i + k; j++) {
      for (auto [val, id] : who[j]) {
        if (!taken[id]) {
          sum += val;
          taken[id] = 1;
          break;
        }
      }
    }
    if (sum > res) {
      res = sum;
    }
    taken.clear(), sum = 0;
  }
  cout << res << "\n";
}

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