//qoj 9457
//https://qoj.ac/contest/1807/problem/9457
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=3e3+5;
int TT,n,m,a[N],tot,p[N];bool v[N],in[N];
vector<int>g[N];
bool dfs(int x)
{
	v[x]=1;
	for(int i:g[x]) if(!v[i])
	{
		v[i]=1;
		if(!p[i]||dfs(p[i])) return p[i]=x,p[x]=i,1;
	}return 0;
}
namespace Prime
{
	const int N=2e6+5;
	int pr[N];bool v[N];
	inline void init(int M)
	{
		for(int i=2;i<=M;i++)
		{
			if(!v[i]) pr[++pr[0]]=i;
			for(int j=1;j<=pr[0]&&i*pr[j]<=M;j++)
			{
				v[i*pr[j]]=1;
				if(i%pr[j]==0) break;
			}
		}fill(v+1,v+1+M,0);
		for(int i=1;i<=pr[0];i++) v[pr[i]]=1;
	}
	inline bool chk(int x){return v[x];}
}using Prime::chk;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>TT;Prime::init(2e6);
	while(TT--)
	{
		cin>>n>>m;int ans=0;
		for(int i=1;i<=n;i++) cin>>a[i],g[i].clear(),p[i]=-1;
		for(int i=1;i<=n;i++) for(int j=1;j<i;j++) if(chk(a[i]+a[j]))
			g[i].push_back(j),g[j].push_back(i),p[i]=p[j]=0;
		for(int i=1;i<=n;i++) if(!p[i]) fill(v+1,v+1+n,0),ans+=dfs(i); 
		if(m<=ans) cout<<2*m<<"\n";
		else
		{
			int res=0;
			for(int i=1;i<=n;i++) res+=(!p[i]);
			cout<<2*ans+min(res,m-ans)<<"\n";
		}
	}
	return 0;
}