#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll>                   PII;
const int sz = 6 * 10e3 + 5;
int parent[sz] , sizeofNode[sz] , n , k ;
int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
    int x = find_set(a);
    int y = find_set(b);

    if (x != y) {
        if (sizeofNode[x] < sizeofNode[y])
            swap(x, y);
        parent[y] = x;
        sizeofNode[x] += sizeofNode[y];
    }
}
bool withinRange(int i , int j ,int k){
    return (i <= k  && k <= j) ? 1 : 0 ;
}
void solve()
{
   cin >> n >> k ; ll a[n + 5] , Ans = 0;
   priority_queue < int > pq[n + 5] , tempPq[n + 5] ;
   vector < int > disjointArray[n + 5] ;
   set < int > pos ;
   for(int i = 1 ; i <= n ; i++){
    parent[i] = i , sizeofNode[i] = 1 , cin >> a[i] ;
    disjointArray[i].clear() ;
    pq[i] = priority_queue < int > () ;
   }
   for(int i = 1 ; i <= n  ; i++){
    for(int j = i ; j <= n ; j++){
        if(__gcd(a[i] , a[j]) > 1) union_sets(i , j) ;
    }
   }
   for(int i = 1 ; i <= n ; i++){
        int par = find_set(i) ;
     disjointArray[par].pb(i) ;
     pos.insert(par) ;
   }
  // for(auto it : pos) cout << it << " " ; cout << endl ;

  /* for(int i = 1 ; i <= n ; i++){
    for(auto it : disjointArray[i]) cout << it << " " ;
    cout << endl ;
   } */

   for(int i = 1 ; i <= n ; i++){
    for(auto it : disjointArray[i]){
        pq[i].push(a[it]) ;
    }
   }

   /*  for(int i = 1 ; i <= n ; i++){
        cout << i << " printing... " << endl ;
       while(!pq[i].empty()){
        cout << pq[i].top() << " " ;
        pq[i].pop() ;
       }
     cout << endl ;

   } */

   for(int i = 1 ; i <= n - k + 1 ; i++){
        ll tempSum = 0 , cnt = 0 ;
       // cout << "range " << i << " " << i + k - 1 << endl ;
      for(auto it : pos){
            if(cnt == k) break ;
            tempPq[it] = pq[it] ;
         //   cout <<it << " printing" << endl ;
        for(auto kt : disjointArray[it]){
            if(withinRange(i , i + k - 1 , kt) && cnt < k){
            //    cout << pq[it].top() << " " ;
                tempSum += pq[it].top() ;
                pq[it].pop() ;
                cnt++ ;
            }
           if (cnt == k) break ;
        }
        pq[it] = tempPq[it] ;
      //  cout << endl ;
      }
      Ans = max(Ans , tempSum) ;
    //  cout << i << " ---- " << Ans << endl ;
   }
   cout << Ans << "\n" ;

}
int main()
{
     __Heart__
     int t ; cin >> t ; while(t--) solve() ;
}