#include<bits/stdc++.h>
using namespace std;
const long long M=2e4+10,MOD=1000000007;
typedef long long ll;
int p[M];
int r[M];
vector<ll>vec[M],val[M];
int find(int x){
    if(p[x]==x)return x;
    else return find(p[x]);
}
void combine(int x,int y){
int a=find(x);
int b=find(y);
if(a==b)return;
if(r[a]>r[b]){
    r[a]+=r[b];
    p[b]=a;
}
else{
    r[b]+=r[a];
    p[a]=b;
}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--){
      int n,k;
      cin>>n>>k;
      vector<ll>a(n+1);
      for(int i=1;i<=n;i++)cin>>a[i];
      for(int i=1;i<=n;i++)p[i]=i,r[i]=1;
      for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            int gd=__gcd(a[i],a[j]);
            if(gd>1){
                combine(i,j);
            }
        }
      }
      for(int i=1;i<=n;i++){
        int x=find(i);
        vec[x].push_back(i);
      }
      for(int i=1;i<=n;i++){
        vector<ll>v;
        for(auto it:vec[i]){
            v.push_back(a[it]);
            //cout<<it<<" ";
        }
        sort(v.rbegin(),v.rend());
        for(auto it:v)val[i].push_back(it);
           // cout<<endl;

      }

     ll mx=0;
     for(int i=1;i<=n;i++){
        int l=i;
        int r=i+k-1;
        int cnt=0;
        ll sum=0;
      //  cout<<"index"<<i<<"\n";
        for(int j=1;j<=n;j++){
            cnt=0;
        for(auto it:vec[j]){
            if(it>=l && it<=r){
               // cout<<val[j][cnt]<<" ";
                sum+=val[j][cnt];
                cnt++;
            }
        }
       // cout<<d<<endl;
    }
       //cout<<d<<endl;
        mx=max(mx,sum);
     }
     cout<<mx<<"\n";
     for(int i=1;i<=n;i++){
        vec[i].clear();
        val[i].clear();
     }

     

    }




    
   
   return 0;
 
}