// created:  2024-10-12 09:27:04
#include<cstdio>
#include<cctype>
#include<algorithm>
#define F(i,l,r) for(int i=l,i##_end=r;i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int N=3005,M=2e6;
bool pri[M],g[N][N];
int n,k,n2,a1[N],a2[N],ma[N],ima[N],d[N],q[N],qf,qr;
bool v1[N],v2[N],vis[N];
bool dfs(int u)
{
	F(v,0,n2)if(g[u][v])
	{
		if(!~ima[v])return ima[ma[u]=v]=u,d[u]=-1,true;
		else if(d[ima[v]]==d[u]+1&&dfs(ima[v]))return ima[ma[u]=v]=u,d[u]=-1,true;
	}
	d[u]=-1;
	return false;
}
bool bfs(int n1)
{
	F(i,0,n1)d[i]=-1;
	qf=qr=0;
	F(i,0,n1)if(!~ma[i])d[q[qr++]=i]=0;
	while(qf<qr)
	{
		int u=q[qf++];
		F(v,0,n2)if(g[u][v])
		{
			if(!~ima[v])return true;
			else if(!~d[ima[v]])d[q[qr++]=ima[v]]=d[u]+1;
		}
	}
	return false;
}
int run(int n1)
{
	int ans=0;
	while(bfs(n1))F(i,0,n1)if(!d[i])ans+=dfs(i);
	return ans;
}
int n1;
void solve()
{
	read(n,k);
	int rn=0;
	n1=n2=0;
	int one=0;
	F(i,0,n)
	{
		int a;read(a);
		if(a==1)++one;
		else if(a&1)a1[n1++]=a;
		else a2[n2++]=a;
	}
	F(i,0,one)a1[n1++]=1;
	F(i,0,n1)v1[i]=false;
	F(i,0,n2)v2[i]=false;
	if(one>1)F(i,n1-one,n1)v1[i]=true;
	F(i,0,n1)F(j,0,n2)if((g[i][j]=pri[a1[i]+a2[j]]))v1[i]=v2[j]=true;
	F(i,0,n1)rn+=v1[i];
	F(i,0,n2)rn+=v2[i];
	F(i,0,n1)ma[i]=-1;
	F(i,0,n2)ima[i]=-1;
	int m1=run(n1-one);
	int m2=run(n1);
	int mm=m1+m2+((one-m2)>>1);
	int ans=min(min(k,mm)+k,rn);
	printf("%d\n",ans);
}
int main()
{
	F(i,2,M)pri[i]=true;
	F(i,2,M)if(pri[i])for(int j=2*i;j<M;j+=i)pri[j]=false;
	int tt;read(tt);
	while(tt--)solve();
	return 0;
}