#include<bits/stdc++.h>
using namespace std;

int bin_pow(int a, int b){
    int ans=1;
    while(b){
        if(b&1){
            ans*=a;
        }
        a*=a;
        b>>=1;
    }
    return ans;
}

int ch[10000005];
vector<int> f(10000005,-1);

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i=2; i<=10000000; i++){
        if(ch[i]) continue;
        for(int j=2*i; j<=10000000; j+=i) ch[j]=i;
    }
    vector<int> prim;
    for(int i=2; i<=10000000; i++) if(!ch[i]) prim.push_back(i);
    for(auto it:prim) f[it]=1;
    for(int i=4; i<=10000000; i++){
        if(i%2==0) f[i]=2;
        else{
            if(f[i-2]==1 && f[i]==-1) f[i]=2;
        }
    }
    for(int i=2; i<=10000000; i++) if(f[i]==-1) f[i]=3;
    int t;
    cin>>t;
    while(t--){
        int n, k;
        cin>>n>>k;
        int arr[n];
        for(int i=0; i<n; i++) cin>>arr[i];
        vector<int> v;
        for(int i=0; i<n; i++) v.push_back(f[arr[i]]);
        sort(v.begin(),v.end());
        int ans=k;
        for(int i=0; i<n-k; i++) ans+=v[i];
        cout<<ans<<'\n';
    }
}