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

const int N = 6e3+10, M =1.5e7+10;

class Maxflow{
private:
    int nedge = 1,p[2*M],nex[2*M],head[N],c[2*M],cur[2*M];
    int dist[2*N];
    int S,T;
    void Addedge(int a,int b,int v){
        p[++nedge] = b;
        nex[nedge] = head[a];
        head[a] = nedge;
        c[nedge] = v;
    }
    bool bfs(){
        queue<int> q;
        for (int i = S; i <= T; i++){
            dist[i] = -1;
        }
        dist[S] = 0;
        q.push(S);
        while(!q.empty()){
            int now = q.front();
            q.pop();
            // cout<<"now="<<now<<" dist="<<dist[now]<<endl;
            for (int k = head[now]; k ; k =nex[k])
                if (dist[p[k]] == -1 && c[k] > 0){
                    dist[p[k]] = dist[now]+1;
                    q.push(p[k]);
                }
            
        }
        return dist[T] > -1;
    }
    int dfs(int x,int low){
        if (x == T)
            return low;
        if (low == 0)
            return 0;
        int used = 0;
        for (int&k = cur[x]; k ; k = nex[k])
            if (dist[p[k]] == dist[x] + 1 && c[k] > 0){
                int a = dfs(p[k],min(c[k],low-used));
                c[k] -= a;
                c[k^1] += a;
                used += a;
                if (low == used)
                    break;
            }
        if (used == 0){
            dist[x] = -1;
        }
        return used;
    }
public:
    void init(int s,int t){
        for(int i=S;i<=T;i++)head[i]=0;
        S=s,T=t;
        nedge = 1;
    }
    void addedge(int a,int b,int v){
        // cout<<"a="<<a<<" b="<<b<<" v="<<v<<endl;
        Addedge(a,b,v);
        Addedge(b,a,0);
    }
    int dinic(){
        int flow = 0;
        while(bfs()){
            // cout<<"flow="<<flow<<endl;
            for (int i = S; i <= T; ++i)
                cur[i] = head[i];
            flow += dfs(S,1e9);
        }
        return flow;
    }
}sol;

int f[2000'010];
int solve()
{
    int n,k;cin>>n>>k;
    vector<int> v1,v2,v3;
    int cnt1=0;
    vector<int>all(n);
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        all[i-1]=x;
        if(x==1)cnt1++;
        else if(x%2==1)v1.push_back(x);
        else v2.push_back(x);
    }
    int tot=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)if(i!=j){
            if(!f[all[i]+all[j]]){
                tot++;break;
            }
        }
    }
    int nowans=0;
    int s=0,t=v1.size()+v2.size()+1;
    sol.init(s,t);
    for(int i=1;i<=v1.size();i++)sol.addedge(s,i,1);
    for(int i=1;i<=v2.size();i++)sol.addedge(i+v1.size(),t,1);
    for(int i=1;i<=v1.size();i++){
        for(int j=1;j<=v2.size();j++)if(f[v2[j-1]+1]&&!f[v1[i-1]+v2[j-1]]){
            sol.addedge(i,j+v1.size(),1);
        }
    }
    int ok1=0;
    for(auto it:v2)if(!f[it+1])ok1++;
    int ans1=sol.dinic();
    for(int i=1;i<=v1.size();i++){
        for(int j=1;j<=v2.size();j++)if(!f[v2[j-1]+1]&&!f[v1[i-1]+v2[j-1]]){
            sol.addedge(i,j+v1.size(),1);
        }
    }
    int ans2=sol.dinic();
    nowans=ans1+ans2;
    ok1-=ans2;
    // cout<<"ans1="<<ans1<<" ans2="<<ans2<<" ok1="<<ok1<<" cnt1="<<cnt1<<endl;
    nowans+=min(cnt1,ok1);{int g=min(cnt1,ok1);ok1-=g,cnt1-=g;}
    nowans+=cnt1/2;
    nowans*=2;
    if(nowans>=2*k)return 2*k;
    return min(tot,k-nowans/2+nowans);
}
signed main()
{
    f[1]=1;
    for(int i=2;i<=2000000;i++)if(!f[i]){
        for(int j=i*2;j<=2000000;j+=i)f[j]=1;
    }
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--){
        cout<<solve()<<"\n";
    }
}

/*
4
4 2
2 3 4 5
5 3
3 4 12 3 6
6 3
1 3 6 8 1 1
1 0
1


1
6 3
1 3 6 8 1 1
*/