#include <bits/stdc++.h>
using namespace std;
const int N=3005,M=2e6+5;
int n,k,a[N],p[M],c[N],b[N];
vector<int> e[N];
bool dfs(int x,int v){
	b[x]=v;
	for(int y:e[x]) if(b[y]!=v){
		b[y]=v;
		if(!c[y]||dfs(c[y],v)){
			c[y]=x;c[x]=y;
			return 1;
		}
	}
	return 0;
}
void solve(){
	cin>>n>>k;
	memset(c,-1,sizeof c);
	memset(b,0,sizeof b);
	for(int i=1;i<=n;i++) cin>>a[i],e[i].clear();
	int s1=0,s2=0;
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(!p[a[i]+a[j]])
		e[i].push_back(j),e[j].push_back(i),c[i]=c[j]=0;
	for(int i=1;i<=n;i++) if(!c[i]&&dfs(i,i)) s1++;
	for(int i=1;i<=n;i++) if(!c[i]) s2++;
	cout<<(s1>=k?k*2:s1*2+min(k-s1,s2))<<"\n";
}
int main(){
	cin.tie(0)->sync_with_stdio(0);
	for(int i=2;i<M;i++) if(!p[i]) for(int j=i*2;j<M;j+=i) p[j]=1;
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}