#include<bits/stdc++.h>
#define inl inline
using namespace std;
const int N=3005,IB=1<<21; char IN[IB],*IS=IN+IB,*IT=IS;
#define getchar() (IS==IT&&(IT=IN+fread(IS=IN,1,IB,stdin)),IS==IT?EOF:*IS++)
int n,T,mt[N],un[N],fr[N],vs[N],vt[N]; vector<int> e[N]; queue<int> q;
inl int Read()
{
	int s=0; char c; while(!isdigit(c=getchar()));
	for(;isdigit(c);c=getchar()) s=s*10+c-'0'; return s;
}
inl int Uni(int p) {return p==un[p]?p:un[p]=Uni(un[p]); }
inl int LCA(int x,int y)
{
	for(++T,x=Uni(x),y=Uni(y);vt[x]!=T;vt[x]=T,x=Uni(fr[mt[x]]),y&&(x^=y^=x^=y));
	return x;
}
inl void BLS(int x,int y,int t)
{
	for(;Uni(x)!=t;x=fr[y])
	{
		fr[x]=y; vs[y=mt[x]]==2&&(q.push(y),vs[y]=1);
		x==Uni(x)&&(un[x]=t); y==Uni(y)&&(un[y]=t);
	}
}
inl int Find(int p)
{
	while(!q.empty()) q.pop(); for(int i=1;i<=n;++i) vs[un[i]=i]=0;
	q.push(p); vs[p]=1; for(int u,t;!q.empty();q.pop())
		for(int v:e[u=q.front()]) if(Uni(u)!=Uni(v)&&vs[v]!=2)
		{
			if(vs[v]) BLS(u,v,t=LCA(u,v)), BLS(v,u,t);
			else
			{
				vs[v]=2; fr[v]=u; if(mt[v]) q.push(mt[v]), vs[mt[v]]=1;
				else {for(;v;v=t) t=mt[fr[v]], mt[mt[v]=fr[v]]=v; return 1; }
			}
		}
	return 0;
}
int k;
int a[N];
bool vis[2000005];
void init(int x){
	for(int i=2;i<=x;i++)
		for(int j=i+i;j<=x;j+=i)
			vis[j]=1;
}
void sol(){
	n=Read(),k=Read();
	for(int i=1;i<=n;i++)a[i]=Read();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			if(!vis[a[i]+a[j]])
				e[i].push_back(j);
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i) ans+=!mt[i]&&Find(i);
	int sum=0;for(int i=1;i<=n;i++)if(e[i].size())sum++;
	if(k<=ans)cout<<k*2<<'\n';
	else cout<<min(k+ans,sum)<<'\n';
	while(!q.empty())q.pop();
	fill(mt+1,mt+n+2,0);
	fill(un+1,un+n+2,0);
	fill(fr+1,fr+n+2,0);
	fill(vs+1,vs+n+2,0);
	fill(vt+1,vt+n+2,0);
	for(int i=1;i<=n+1;i++)e[i].clear();
	n=T=0;
}
signed main()
{
	init(2e6);
	int TT=Read();
	while(TT--)sol();
	return 0;
}