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

typedef long long ll;
#define pb push_back
const ll N=1e4+3,INF=(ll)1e18;
struct Flow
{
	ll tot=-1;
	vector<ll>ve[N],to,lim,val; 
	int Add(int x,int y,ll z,ll w)
	{
		ve[x].pb(++tot);to.pb(y);lim.pb(z);val.pb(w);
		ve[y].pb(++tot);to.pb(x);lim.pb(0);val.pb(-w);
		return tot-1;
	}
	ll S,T,cost,dis[N],cur[N];
	bool vis[N];
	bool Spfa()
	{
		memset(cur,0,sizeof(cur));
		memset(dis,0x3f,sizeof(dis));
		memset(vis,0,sizeof(vis));
		queue<int>q;dis[S]=0;q.push(S);
		while(!q.empty())
		{
			int x=q.front();q.pop();vis[x]=0;
			for(int id:ve[x])if(dis[to[id]]>dis[x]+val[id]&&lim[id])
			{
				dis[to[id]]=dis[x]+val[id];
				if(!vis[to[id]])q.push(to[id]),vis[to[id]]=1;
			}
		}
		return dis[T]<INF;
	}
	ll Dfs(ll x,ll res)
	{
		if(x==T)return res;
		ll flow=0;vis[x]=1;
		for(int i=cur[x];i<(int)ve[x].size()&&res;i++)
		{
			cur[x]=i;ll id=ve[x][i],y=to[id],w=min(res,lim[id]),z;
			if(!vis[y]&&dis[x]+val[id]==dis[y]&&w)
			    z=Dfs(y,w),flow+=z,res-=z,lim[id]-=z,lim[id^1]+=z,cost+=z*val[id];
		}
		if(!flow)dis[x]=INF;
		vis[x]=0;return flow;
	}
	ll Maxflow(int s,int t)
	{
		S=s;T=t;ll flow=0;cost=0;
		while(Spfa())flow+=Dfs(S,INF);
		return flow;
    }
    void Clear(int sum)
    {
    	for(int i=0;i<=sum;i++)ve[i].clear();
    	to.clear();lim.clear();val.clear();tot=-1;
	}
}G;
const int K=2e6+3;
int n,KK,S,T,cnt,a[N],b[N],c[N],pri[K];
bool vis[K];
void Solve()
{
	cin>>n>>KK;int S=n+1,T=S+1;int m=0;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=c[i]=0;
	sort(a+1,a+n+1);G.Clear(T);
	for(int i=1;i<=n;i++)if(a[i]==1)m=i;
	for(int i=m+1;i<=n;i++)if(a[i]%2==0)b[i]=G.Add(S,i,1,0);else b[i]=G.Add(i,T,1,0);
	for(int i=m+1;i<=n;i++)for(int j=i+1;j<=n;j++)if(!vis[a[i]+a[j]])
	{
		int x=i,y=j;
		if(a[x]%2==1)swap(x,y);
		G.Add(x,y,1,1+(vis[a[x]+1]==0));c[x]=c[y]=1;
	}
	int flow=G.Maxflow(S,T);vector<int>cur;
	int nb[2]={0},kk=0,mk=0;
	if(!m)
	{
		if(flow>=KK){cout<<KK*2<<endl;return;}
		for(int i=m+1;i<=n;i++)if(G.lim[b[i]]&&c[i])kk++;
		cout<<flow*2+min(KK-flow,kk)<<endl;return;
	}
	for(int i=1;i<=n;i++)if(a[i]%2==0&&G.lim[b[i]])cur.push_back(i);
	sort(cur.begin(),cur.end(),[&](int X,int Y){return c[X]<c[Y];});
	for(int x:cur)if(!vis[a[x]+1])
	{
		if(m)m--,nb[c[x]]++,c[x]=0;
		else kk++,c[x]=0; 
	}
	for(int i=m+1;i<=n;i++)if(G.lim[b[i]]&&c[i])kk++;
	flow+=m/2+nb[0]+nb[1];
	if(m%2==1)for(int i=2;i<=n;i++)mk|=!vis[a[i]+1]; 
	if(flow>=KK){cout<<KK*2<<endl;return;}
	cout<<flow*2+min(KK-flow,kk+mk)<<endl;
}
void Init()
{
	for(int i=2;i<K;i++)
	{
		if(!vis[i])pri[++cnt]=i;
		for(int j=1;j<=cnt&&pri[j]*i<K;j++)
		{
			vis[pri[j]*i]=1;
			if(i%pri[j]==0)break;
		}
	}
}
int main()
{
    int _;cin>>_;Init();
    while(_--)Solve();
}