#include <bits/stdc++.h>
using namespace std;
const int N=3e3+5,M=2e6+5;
int T,n,n1,n2,n3,m,a[N],a1[N],a2[N],p[M];bool vs[M];
int w,w1,mch[N];bitset<N> tg,e[N];
void sieve(int n)
{
    for(int i=2;i<=n;++i)
    {
        if(!vs[i]) p[++p[0]]=i;
        for(int j=1;i*p[j]<=n;++j)
        {vs[i*p[j]]=1;if(!(i%p[j])) break;}
    }
}
bool dfs(int u)
{
    while(1)
    {
        bitset<N> z=e[u]&tg;int v=z._Find_first();
        if(v==N) return 0;tg.reset(v);
        if(!mch[v] || dfs(mch[v])) {mch[v]=u;return 1;}
    }
}
void slv()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n1;++i) e[i].reset();
    n1=n2=n3=w=w1=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        if(a[i]==1) ++n3;
        else if(a[i]&1) a1[++n1]=a[i];else a2[++n2]=a[i];
    }
    for(int i=1;i<=n1;++i) for(int j=1;j<=n2;++j)
        if(!vs[a1[i]+a2[j]]) e[i].set(j);
    fill(mch+1,mch+n2+1,0);
    for(int i=1;i<=n1;++i) tg.set(),w+=dfs(i);
    w1=max(w1,w+n3/2);
    for(int i=1;i<=n3;++i)
    {
        a1[++n1]=1;
        for(int j=1;j<=n2;++j) if(!vs[a2[j]+1]) e[n1].set(j);
        tg.set();w+=dfs(n1);w1=max(w1,w+(n3-i)/2);
    }
    w=0;
    for(int i=1;i<=n;++i)
    {
        bool fl=0;
        for(int j=1;j<=n;++j)
            if(i!=j && !vs[a[i]+a[j]]) {fl=1;break;}w+=fl;
    }
    printf("%d\n",m<=w1?m*2:min(m+w1,w));
}
int main()
{
    sieve(2e6);scanf("%d",&T);
    while(T--) slv();return 0;
}