#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e6;
int T,n,m,a[3010],p[3010];
bool mark[N+10];
vector<int> v[2];
bitset<3010> e[3010],V;
bool dfs(int now)
{
	while(1)
	{
		int t=(e[now]&V)._Find_first();
		if(t>v[1].size())
		{
			return 0;
		}
		V.reset(t);
		if(p[t]<0||dfs(p[t]))
		{
			p[t]=now;
			return 1;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	for(int i=2;i<=N;i++)
	{
		if(!mark[i])
		{
			for(int j=i<<1;j<=N;j+=i)
			{
				mark[j]=1;
			}
		}
	}
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		v[0].clear(),v[1].clear();
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			v[a[i]+1&1].emplace_back(a[i]);
		}
		int cnt=n,ans=0,f=0;
		for(int i=1;i<=n;i++)
		{
			bool flag=1;
			for(int j=1;j<=n;j++)
			{
				if(i==j)
				{
					continue;
				}
				if(!mark[a[i]+a[j]])
				{
					flag=0;
					break;
				}
			}
			cnt-=flag;
		}
		sort(v[0].begin(),v[0].end());
		sort(v[1].begin(),v[1].end());
		for(int i=0;i<v[0].size();i++)
		{
			e[i].reset();
			for(int j=0;j<v[1].size();j++)
			{
				if(!mark[v[0][i]+v[1][j]])
				{
					e[i].set(j);
				}
			}
		}
		memset(p,-1,sizeof(p));
		for(int i=v[0].size()-1;i>=0;i--)
		{
			V.set();
			if(dfs(i))
			{
				ans++;
			}
			else
			{
				if(v[0][i]==1)
				{
					f=i+1>>1;
					break;
				}
				int j=i-1;
				while(j>=0&&v[0][j]==v[0][i])
				{
					j--;
				}
				i=j+1;
			}
		}
		ans+=f;
		if(m>=ans)
		{
			int t=(ans<<1)+m-ans;
			cout<<min(cnt,t)<<'\n';
			continue;
		}
		cout<<(m<<1)<<'\n';
	}
	return 0;
}