#include<bits/stdc++.h>
using namespace std;
constexpr int N=3005,M=2000005;
bool isprime[M];
void init(int n=2000000)
{
    fill(isprime+1,isprime+n+1,true);
    isprime[1]=false;
    for(int i=2;i<=n;i++)
        if(isprime[i])
        {
            for(int j=i+i;j<=n;j+=i)
                isprime[j]=false;
        }
    return;
}
struct Hopcroft_Karp
{
    int n,m;
    vector<int>g[N];
    int pa[N],pb[N];
    Hopcroft_Karp(){}
    Hopcroft_Karp(int _n,int _m):n(_n),m(_m){}
    void init(int _n,int _m)
    {
        n=_n,m=_m;
        for(int i=1;i<=n;i++)
            g[i].clear();
        return;
    }
    void add_edge(int u,int v)
    {
        g[u].push_back(v);
        return;
    }
    int dis[N];
    bool bfs()
    {
        queue<int>q;
        for(int u=1;u<=n;u++)
        {
            if(!pa[u])
            {
                dis[u]=0;
                q.push(u);
            }
            else dis[u]=-1;
        }
        bool found=false;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int v:g[u])
            {
                if(pb[v]&&dis[pb[v]]==-1)
                {
                    dis[pb[v]]=dis[u]+1;
                    q.push(pb[v]);
                }
                else if(!pb[v]) found=true;
            }
        }
        return found;
    }
    bool dfs(int u)
    {
        for(int v:g[u])
            if(!pb[v]||(dis[pb[v]]==dis[u]+1&&dfs(pb[v])))
            {
                pa[u]=v,pb[v]=u;
                return true;
            }
        dis[u]=-1;
        return false;
    }
    int max_matching()
    {
        fill(pa+1,pa+n+1,0);
        fill(pb+1,pb+m+1,0);
        int res=0;
        while(bfs())
        {
            for(int u=1;u<=n;u++)
                if(!pa[u]&&dfs(u)) res++;
        }
        return res;
    }
};
int n,k;
int a[N];
int vl[N],totl;
int vr[N],totr;
Hopcroft_Karp solver;
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    totl=totr=0;
    for(int i=1;i<=n;i++)
        if(a[i]&1) vl[++totl]=a[i];
        else vr[++totr]=a[i];
    solver.init(totl,totr);
    for(int i=1;i<=totl;i++)
        for(int j=1;j<=totr;j++)
            if(isprime[vl[i]+vr[j]]) solver.add_edge(i,j);
    int y=solver.max_matching();
    totl=totr=0;
    int cnt=0;
    for(int i=1;i<=n;i++)
        if(a[i]>1)
        {
            if(a[i]&1) vl[++totl]=a[i];
            else vr[++totr]=a[i];
        }
        else cnt++;
    solver.init(totl,totr);
    for(int i=1;i<=totl;i++)
        for(int j=1;j<=totr;j++)
            if(isprime[vl[i]+vr[j]]) solver.add_edge(i,j);
    int x=solver.max_matching();
    int m1=y+(cnt-(y-x))/2;
    int m2=0;
    for(int i=1;i<=n;i++)
    {
        bool flag=false;
        for(int j=1;j<=n;j++)
            if(i!=j&&isprime[a[i]+a[j]])
            {
                flag=true;
                break; 
            }
        if(flag) m2++;
    }
    int ans=k;
    ans+=min(m1,k);
    ans=min(ans,m2);
    cout<<ans<<"\n";
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    init();
    int T;
    cin>>T;
    while(T--)
        solve();
    return 0;
}