#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<string>

#include<set>

#include<algorithm>

#include<vector>

#include<queue>

#include<list>

#include<cmath>

#include<cstring>

#include<map>

#include<stack>

using namespace std;

#define INF 0x3f3f3f3f

#define maxn 2000005

#define ull unsigned long long

#define ll long long

#define hashmod 99999839

#define mod 9997

bool isprim[maxn],f[];

int pre[];

int prim[maxn],len,a[];

vector<int> vec[];

void init(){

    for(int i = ;i < maxn;i++) isprim[i] = true;

    for(int i = ;i < maxn;++i){

        if(isprim[i]) prim[len++] = i;

        for(int j = ;j < len;++j){

            if(i * prim[j] > maxn) break;

            isprim[i * prim[j]] = false;

            if(i % prim[j] == ) break;

        }

    }

}

bool dfs(int v){//尝试匹配v

    f[v] = true;

    for(int i = ;i < vec[v].size();++i){

        int t = vec[v][i];

        if(!f[t]){

            f[t] = true;

            if(!pre[t] || dfs(pre[t])){

                pre[t] = v;

                pre[v] = t;

                f[t] = false;

                f[v] = false;

                return true;

            }

        }

    }

    return false;

}

int main(){

  //  freopen("a.in","r",stdin);

 //   freopen("b.out","w",stdout);

    init();

    int T;

    cin >> T;

    int n,k;

    while(T--){

        scanf("%d%d",&n,&k);

        for(int i = ;i <= n;++i){

            scanf("%d",&a[i]);

        }

        sort(a + ,a + n + );

        for(int i = ;i <= n;++i){

            for(int j = i + ;j <= n;++j){

                if(isprim[a[i] + a[j]]) vec[i].push_back(j),vec[j].push_back(i);

            }

        }

        memset(f,false,sizeof(f));

        memset(pre,,sizeof(pre));

        int ans = ;

        for(int i = ;i <= n;++i){

            if(!pre[i] && !f[i] && dfs(i)){

                ans++;

            }

        }

        if(ans >= k) ans = k * ;

        else{

            k -= ans;

            ans = ans * ;

            for(int i = ;i <= n && k;++i){

                if(!pre[i]){

                    int sz = vec[i].size();

                    if(sz) k--,ans++;

                }

            }

        }

        for(int i = ;i <= n;++i) vec[i].clear();

        printf("%d\n",ans);

    }

    return ;

}