#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;
bool notPrime[sz] ;
int parent[sz] , sizeofNode[sz] , n , k ;
vector < int > prime ;
map < int , set < int >> mp ;
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 ;
}

int gcd(int a, int b)
{
    if (a == b) return a;
    if (a == 0) return b;
    if (b == 0) return a;

    if (~a & 1)
    {
        if (b & 1) return gcd(a >> 1, b);
        else return gcd(a >> 1, b >> 1) << 1;
    }

    if (~b & 1) return gcd(a, b >> 1);
    if (a > b) return gcd((a - b) >> 1, b);
    return gcd((b - a) >> 1, a);
}
void seive()
{
    for(int  i = 4 ; i < sz ; i += 2) notPrime[i] = 1 ;
    int k = sqrt(sz);
    for(int i = 3 ; i < k ; i += 2)
    {
        for(int j = i*i ; j < sz ; j += i) notPrime[j] = 1 ;
    }
    prime.pb(2) ;
    for(int i = 3  ; i < sz ; i += 2) if(!notPrime[i]) prime.pb(i) ;
}
void primefactor(int n , int pos)
{
    for(int i = 0; prime[i] <= sqrt(n) && i < prime.size(); i++)
    {
        if(n % prime[i] == 0)
        {
            while(n % prime[i] == 0) n /= prime[i] ;
            mp[prime[i]].insert(pos) ;
        }
    }
    if(n != 1) mp[n].insert(pos);

}

void solve()
{
   cin >> n >> k ; int a[n + 5]; ll Ans = 0 ;
   vector < int > disjointArray[n + 5] , v[n + 5];
   multiset < int , greater < > > temp ;
   set < int > pos ;
   mp.clear() ;
   for(int i = 1 ; i <= n ; i++){
    parent[i] = i , sizeofNode[i] = 1 , cin >> a[i] , primefactor(a[i] , i);
    disjointArray[i].clear() ;
    v[i].clear() ;
   }

   /*for(int i = 1 ; i <= n  ; i++){
    for(int j = i + 1 ; j <= n ; j++){
        if(gcd(a[i] , a[j]) > 1) union_sets(i , j) ;
    }
   }*/

   for(auto it : mp){
        int firstValue = 0 ;
       for(auto kt : mp[it.F]){
        if(firstValue) union_sets(firstValue , kt) ;
        else firstValue = kt,union_sets(firstValue , kt)  ;
       }
   }

   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(auto it : pos){
    for(auto kt : disjointArray[it]) cout << kt << " " ;
    cout << endl ;
   } */

   for(int i = 1 ; i <= n ; i++){
    for(auto it : disjointArray[i]){
        temp.insert(a[it]) ;
    }
    for(auto it : temp) v[i].pb(it) ;
    temp.clear() ;
   }

   /*  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 , p = 0;
       // cout << "range " << i << " " << i + k - 1 << endl ;
      for(auto it : pos){
            if(cnt == k) break ;
            p = 0 ;
         //   cout <<it << " printing" << endl ;
        for(auto kt : disjointArray[it]){
            if(withinRange(i , i + k - 1 , kt) && cnt < k){
            //    cout << pq[it].top() << " " ;
                tempSum += v[it][p] ;
                p++ ;
                cnt++ ;
            }
           if (cnt == k) break ;
        }
      //  cout << endl ;
      }
      Ans = max(Ans , tempSum) ;
    //  cout << i << " ---- " << Ans << endl ;
   }
   cout << Ans << "\n" ;

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